Re: [閒聊] 每日leetcode

[sixB (6B)]

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;
    }
};

--
很姆的咪

姆之咪

http://i.imgur.com/5sw7QOj.jpg

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 110.28.121.165 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1746460760.A.22F.html