Counting Towers

Your task is to build a tower whose width is 2 and height is n. You have an unlimited supply of blocks whose width and height are integers.

Given n, how many different towers can you build? Mirrored and rotated towers are counted separately if they look different.

Example:

Input:  n = 2
Output: 8

Approach

C++

#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 1e6 + 1;
const long long MOD = 1e9 + 7;

vector<array<long long, 2>> dp(MAX_N + 1);

void precompute()
{
    dp[1][0] = dp[1][1] = 1;
    for (int i = 2; i < MAX_N; i++)
    {
        dp[i][0] = (dp[i - 1][1] + 4 * dp[i - 1][0]) % MOD;
        dp[i][1] = (dp[i - 1][0] + 2 * dp[i - 1][1]) % MOD;
    }
}

long long countingTowers(int n)
{

    return (dp[n][0] + dp[n][1]) % MOD;
}

int main()
{

    precompute();

    int n = 2;

    cout << countingTowers(n) << "\n";

    return 0;
}