[Leetcode] Paint Fence 柵欄涂色

sixleaves 發(fā)布于2019-08-14 12:36 / 1211人閱讀

摘要：假設(shè)是第一根柱子及之前涂色的可能性數(shù)量，是第二根柱子及之前涂色的可能性數(shù)量，則。遞推式有了，下面再討論下情況，所有柱子中第一根涂色的方式有中，第二根涂色的方式則是，因?yàn)榈诙涌梢院偷谝桓粯印?/p>

Paint Fence

There is a fence with n posts, each post can be painted with one of the k colors.

You have to paint all the posts such that no more than two adjacent fence posts have the same color.

Return the total number of ways you can paint the fence.

Note: n and k are non-negative integers.

哈希表法 復(fù)雜度

時(shí)間 O(N) 空間 O(1)

思路

這種給定一個(gè)規(guī)則，計(jì)算有多少種結(jié)果的題目一般都是動(dòng)態(tài)規(guī)劃，因?yàn)槲覀兛梢詮倪@個(gè)規(guī)則中得到遞推式。根據(jù)題意，不能有超過連續(xù)兩根柱子是一個(gè)顏色，也就意味著第三根柱子要么根第一個(gè)柱子不是一個(gè)顏色，要么跟第二根柱子不是一個(gè)顏色。如果不是同一個(gè)顏色，計(jì)算可能性的時(shí)候就要去掉之前的顏色，也就是k-1種可能性。假設(shè)dp[1]是第一根柱子及之前涂色的可能性數(shù)量，dp[2]是第二根柱子及之前涂色的可能性數(shù)量，則dp[3]=(k-1)*dp[1] + (k-1)*dp[2]。

遞推式有了，下面再討論下base情況，所有柱子中第一根涂色的方式有k中，第二根涂色的方式則是k*k，因?yàn)榈诙涌梢院偷谝桓粯印?/p> 代碼

public class Solution {
    public int numWays(int n, int k) {
        // 當(dāng)n=0時(shí)返回0
        int dp[] = {0, k , k*k, 0};
        if(n <= 2){
            return dp[n];
        }
        for(int i = 2; i < n; i++){
            // 遞推式：第三根柱子要么根第一個(gè)柱子不是一個(gè)顏色，要么跟第二根柱子不是一個(gè)顏色
            dp[3] = (k - 1) * (dp[1] + dp[2]);
            dp[1] = dp[2];
            dp[2] = dp[3];
        }
        return dp[3];
    }
}