[알고리즘] leetcode 790. 도미노와 트로미노 타일링 c++ // dp

* 완탐

1. 타일의 종류정리하기

2. 상태정의 : 열번호, 이전이 완전한지 여부

long mod = 1e9+7;
int n;

class Solution {
public:
    long dfs(int i, int prevgab){
        if(i==n && prevgab==0){ //success
            return 1;
        }
        if(i==n && prevgab == 1){ //fail
            return 0;
        }
        if(i>n){ //out of index
            return 0;
        }

        //이전열이 빈칸이있는경우, 
        if(prevgab){
            return dfs(i+1,0) +  dfs(i+1,1);
        }
        else{
            return dfs(i+1,0) + dfs(i+2,0) + dfs(i+2,1) + dfs(i+2,1) ; // 2*dfs(i+2,1)로 압축가능
        }
        
    }

    int numTilings(int _n) {
        n=_n;
        return dfs(0,0);
    }
};

- 시간복잡도 : 3^1000(n) // 우리는 매번 최대 3개의 재귀 호출을 분기 -> 불가

 

* dp

상태를 dp에 저장하면된다.

시간복잡도 , 공간복잡도 : O(N)  // 상태가 N개이므로.

long mod = 1e9+7;
int n;
long dp[1004][2]; // 그상태를 만드는 경우의수

class Solution {
public:
    long dfs(int i, int prevgab){
        if(i>n){ //out of index
            return 0;
        }
        if(i==n && prevgab==0){ //success
            return 1;
        }
        if(i==n && prevgab == 1){ //fail
            return 0;
        }
        if(dp[i][prevgab]!=-1){
            return dp[i][prevgab]%mod;
        }

        dp[i][prevgab]=0;
        //이전열이 빈칸이있는경우, 
        if(prevgab){
            return dp[i][prevgab] = (dfs(i+1,0) +  dfs(i+1,1))%mod;
        }
        else{
            return dp[i][prevgab] = (dfs(i+1,0) + dfs(i+2,0) + dfs(i+2,1) + dfs(i+2,1))%mod ;
        }

        return dp[i][prevgab];
        
    }

    int numTilings(int _n) {
        n=_n;
        memset(dp,-1,sizeof(dp));
        return dfs(0,0);
    }
};

 

* 표 dp

class Solution {
public:
	const int MOD = 1e9+7;
    int numTilings(int n) {
        vector<vector<int>> dp(n+2, vector<int>(2));
        dp[1] = {1, 1}, dp[2] = {2, 2};                 // base cases
        for(int i = 3; i <= n; i++) {
            dp[i][0] = (dp[i-1][0] + dp[i-2][0] + 2l*dp[i-2][1]) % MOD;
            dp[i][1] = (dp[i-1][0] + dp[i-1][1]) % MOD;
        }
        return dp[n][0];
    }
};

* 표 dp + 공간최적화

class Solution {
public:
	const int MOD = 1e9+7;
    int numTilings(int n) {
        vector<vector<int>> dp(3, vector<int>(2));  // note only 3 rows are declared
        dp[1] = {1, 1}, dp[2] = {2, 2};
        for(int i = 3; i <= n; i++) {
            dp[i%3][0] = (dp[(i-1)%3][0] + dp[(i-2)%3][0] + 2l*dp[(i-2)%3][1]) % MOD;
            dp[i%3][1] = (dp[(i-1)%3][0] + dp[(i-1)%3][1]) % MOD;
        }
        return dp[n%3][0];
    }
};

* 솔루션출처 : https://leetcode.com/problems/domino-and-tromino-tiling/solutions/1620975/cpython-simple-solution-w-images-explanation-optimization-from-brute-force-to-dp/