Domino and Tromino Tiling Solutions in C++

/// Source : https://leetcode.com/problems/domino-and-tromino-tiling/description/
/// Author : liuyubobobo
/// Time   : 2018-02-24

#include <iostream>
#include <vector>

using namespace std;

/// Dynamic Programming
/// dp[i]: how many ways to fill a 2*i tiles
///
/// Time Complexity: O(N^2)
/// Space Complexity: O(N)
class Solution {

public:
    int numTilings(int N) {

        vector<int> res;
        res.push_back(1); // 0
        res.push_back(1); // 1
        res.push_back(2); // 2

        if(N <= 2)
            return (int)res[N];

        int mod = 1000000007;
        for(int i = 3 ; i <= N ; i ++){
            // .....A      ....AA
            // .....A  and ....BB
            int x = (res[i-1] + res[i-2]) % mod;

            // AA112233..nnB
            // A112233..nnBB and
            // A112233..nnBB
            // AA112233..nnB
            for(int j = 3 ; i - j >= 0; j += 2){
                x = (x + res[i-j]) % mod;
                x = (x + res[i-j]) % mod;
            }

            // AA112233..BB
            // A112233..nnB and
            // A112233..nnB
            // AA112233..BB
            for(int j = 4 ; i - j >= 0; j += 2){
                x = (x + res[i-j]) % mod;
                x = (x + res[i-j]) % mod;
            }

            res.push_back(x);
        }

        return res[N];
    }
};

int main() {

    cout << Solution().numTilings(3) << endl; // 5
    cout << Solution().numTilings(4) << endl; // 11
    cout << Solution().numTilings(7) << endl; // 117
    cout << Solution().numTilings(1000) << endl; // 979232805

    return 0;
}

/// Source : https://leetcode.com/problems/domino-and-tromino-tiling/description/
/// Author : liuyubobobo
/// Time   : 2018-03-07

#include <iostream>
#include <vector>

using namespace std;

/// Dynamic Programming
///
/// dp[i][0]: how many ways to fill a 2*(i-1) tiles plus:
/// .....0
/// .....0
///
/// dp[i][1]: how many ways to fill a 2*(i-1) tiles plus:
/// .....1
/// .....0
///
/// dp[i][2]: how many ways to fill a 2*(i-1) tiles plus:
/// .....0
/// .....1
///
/// dp[i][3]: how many ways to fill a 2*(i-1) tiles plus:
/// .....1
/// .....1
///
/// The answer is dp[N][3]
///
/// Time Complexity: O(N)
/// Space Complexity: O(N)
class Solution {

public:
    int numTilings(int N) {

        vector<vector<int>> res(N+1, vector<int>(4, 0));

        res[0][0] = 0;
        res[0][1] = 0;
        res[0][2] = 0;
        res[0][3] = 1;

        int mod = 1000000007;
        for(int i = 1 ; i <= N ; i ++){

            res[i][0] = res[i-1][3];
            res[i][1] = (res[i-1][0] + res[i-1][2]) % mod;
            res[i][2] = (res[i-1][0] + res[i-1][1]) % mod;
            res[i][3] = 0;
            for(int j = 0 ; j < 4 ; j ++)
                res[i][3] = (res[i][3] + res[i-1][j]) % mod;

            // cout << res[i][0] << " " << res[i][1] << " " << res[i][2] << " " << res[i][3] << endl;
        }

        return res[N][3];
    }
};

int main() {

    cout << Solution().numTilings(3) << endl; // 5
    cout << Solution().numTilings(4) << endl; // 11
    cout << Solution().numTilings(7) << endl; // 117
    cout << Solution().numTilings(1000) << endl; // 979232805

    return 0;
}

/// Source : https://leetcode.com/problems/domino-and-tromino-tiling/description/
/// Author : liuyubobobo
/// Time   : 2018-03-07

#include <iostream>
#include <vector>

using namespace std;

/// Dynamic Programming
/// Optimiaze last solution about space complexity
/// Time Complexity: O(N)
/// Space Complexity: O(1)
class Solution {

public:
    int numTilings(int N) {

        int res[4];

        res[0] = 0;
        res[1] = 0;
        res[2] = 0;
        res[3] = 1;

        int mod = 1000000007;
        for(int i = 1 ; i <= N ; i ++){

            int last_zero = res[0];
            int last_one = res[1];
            int last_two = res[2];

            res[0] = res[3];

            res[3] = last_zero;
            for(int j = 0 ; j < 3 ; j ++)
                res[3] = (res[3] + res[j]) % mod;

            res[1] = (last_zero + last_two) % mod;
            res[2] = (last_zero + last_one) % mod;
        }

        return res[3];
    }
};

int main() {

    cout << Solution().numTilings(3) << endl; // 5
    cout << Solution().numTilings(4) << endl; // 11
    cout << Solution().numTilings(7) << endl; // 117
    cout << Solution().numTilings(1000) << endl; // 979232805

    return 0;
}