790. 多米諾與戳米諾
然後我看不懂為什麼可以 dp[n-1]*2 + dp[n-3]
大家救救我
戳米諾這個命名真的是
非常合理==
dp修好幾次才寫對
r1 是 row1目前佔了幾格
r2 是 row2目前佔了幾格的
class Solution {
public:
int mod = 1e9 + 7;
int numTilings(int n) {
if(n == 1) return 1;
vector<vector<int>> dp(n+1, vector<int>(n+1, -1));
dp[n][n] = 1;
dp[n-1][n] = 0;
dp[n][n-1] = 0;
return play(dp, 0, 0);
}
int play(vector<vector<int>>& dp, int r1, int r2){
//cout << r1 << " " << r2 << '\n';
int n = dp.size() - 1;
if(r1 > n or r2 > n) return 0;
if(dp[r1][r2] >= 0) return dp[r1][r2];
int res = 0;
if(r1 < r2){
res += play(dp, r1+2, r2); res %= mod;
res += play(dp, r1+2, r2+1); res %= mod;
}
if(r1 > r2){
res += play(dp, r1, r2+2); res %= mod;
res += play(dp, r1+1, r2+2); res %= mod;
}
if(r1 == r2){
res += play(dp, r1+1, r2+1); res %= mod;
res += play(dp, r1+2, r2+2); res %= mod;
res += play(dp, r1+2, r2+1); res %= mod;
res += play(dp, r1+1, r2+2); res %= mod;
}
dp[r1][r2] = res;
return res;
}
};