阿祁的部落格

LeetCode 1931 - Painting a grid with three different colors 解題心得( 題目 )

解題概念:DP

心得:第一次寫LeetCode，他寄出程式碼的方式很特別，跟一般的不同，是寄出一個class。

解題方法:我們這次使用輪廓線DP，假設我們以三進位表示，而且0、1、2分別代表一種顏色，則可以透過像01122的方式表達目前的輪廓。至於解法一開始先窮舉第一排，接著之後進行輪廓線DP枚舉每一種輪廓狀態的轉移，最後加總即為答案!

Java參考程式碼(有更好意見可留言於下方，謝謝!)

class Solution {
    public int colorTheGrid(int m, int n) {
        final int p=ip(m);
        final int mod=1000000007;
        long[][] dp=new long[2][p];
        boolean b;
        boolean[] fillcol=new boolean[3];
        Arrays.fill(dp[0],0);
        for(int i=0;i<p;i++) {
            b=true;
            for(int t=m-1;t>0;t--) {
                if((i/ip(t))%3==(i/ip(t-1))%3){
                    b=false;
                    break;
                }
            }
            if(b)dp[0][i]=1;
        }
        int id=0;
        int dk;//去掉轉移的兩位數後的值 例:13221轉移32，dk=10021
        for(int i=1;i<n;i++) {
            //normal
            for(int j=m;j>0;j--) {
                Arrays.fill(dp[id^1],0);
                for(int k=0;k<p;k++) {
                    Arrays.fill(fillcol,true);
                    dk=k-((k/ip(j-1))%3)*ip(j-1);
                    if(j!=m) {
                        fillcol[((k/ip(j))%3)]=false;
                    }
                    fillcol[((k/ip(j-1))%3)]=false;
                    for(int l=0;l<=2;l++) {
                        if(fillcol[l]) {
                            dp[id^1][(dk+ip(j-1)*l)]+=dp[id][k];
                        }
                    }
                }
                for(int k=0;k<p;k++) {
                    dp[id^1][k]%=mod;
                }
                id^=1;    
            }
        }
        long sum=0;
        for(int i=0;i<p;i++) {
            sum+=dp[id][i];
            sum%=mod;
        }
        return (int)sum;
    }
    
    public int ip(int x) {
        return (int)Math.pow(3,x);
    }
}