leetcode 1411. 给 N x 3 网格图涂色的方案数 [阿里2021春招笔试题dp]

男娘i 2022-11-06 00:55 68阅读 0赞

> dp\[i\]\[j\] 表示 第i+1行采用第j种方案染色的时候的方案种数  
> dp\[i\]\]\[j\] = sum(dp\[i-1\]\[k\])  
> dp\[i-1\]\[k\]表示 i行染色j与i-1染色为k方案不冲突  
> n=1 时，只要12种方案  
> n>1时可以从 n-1推过来

#define debug(x) cout<<#x<<": "<<x<<endl;
    using ll = long long;
    ll mod = 1e9+7;
    class Solution { 
    public:
        int numOfWays(int n) { 
            vector<string> t = { "101","202","010","212","020","121",
                                 "012","021","102","120","201","210",};
            vector<vector<int>> can(12);
            
            auto isV = [&](int a,int b){ 
                if(t[a][0]!=t[b][0] && t[a][1] != t[b][1] &&t[a][2]!=t[b][2] ){ 
                    return true;
                }
                return false;
            };
            for(int i = 0; i < t.size();i ++){ 
                for(int j = 0;j < t.size();j ++){ 
                    if(isV(i,j)){ 
                        can[i].push_back(j);
                    }
                }
            }
            
            vector<vector<ll>> dp(n,vector<ll>(12,1));
            
            for(int i=1;i<n;i++){ 
                for(int j=0;j<12;j++){ 
                    dp[i][j] = 0;
                    for(auto k:can[j]){ 
                        dp[i][j] += dp[i-1][k];
                        dp[i][j] %= (mod);
                    }
                    //debug(dp[i][j])
                }
            }
            
            
            int ret = 0;
            for(int i=0;i<12;i++){ 
                ret += dp[n-1][i];
                ret %= mod;
            }
            
            return ret;
        }
    };

![在这里插入图片描述][2021030710491942.png]  
**官方题解还有一种复杂度更改的解法**

[2021030710491942.png]: /images/20221023/071ee0cc9e15433583012abdb7b34181.png