leetcode276 -- Paint Fence

leetcode276 -- Paint Fence

题目


意思是有一排Fence n个, k种color, 要求不能有超过三个连着的Fence有相同的color

解答,用DP,假设前面2个都paint好了的话,dp[1], dp[2], 分别表示paint1和paint2的时候的方案数,那么paint第三个的时候有两种选择,

  • 1 和它前面的color不相同,那么这时候不会有连着三个的相同,所以是(k-1)*dp[2]种,

  • 2 和它前面的color相同,这时候只需要和它前面的前面的不相同即可,是(k-1)*dp[1],

所以综合到一块儿即


dp[3] = (k-1) *(dp[1]+dp[2])

然后初始化是

dp = [0, k, k*k, 0]

其实最后一个是要算的了

代码如下,用java写的



public class Solution {
    public int numWays(int n, int k) {
        // 当n=0时返回0
        int dp[] = {0, k , k*k, 0};
        if(n <= 2){
            return dp[n];
        }
        for(int i = 2; i < n; i++){
            // 递推式:第三根柱子要么根第一个柱子不是一个颜色,要么跟第二根柱子不是一个颜色
            dp[3] = (k - 1) * (dp[1] + dp[2]);
            dp[1] = dp[2];
            dp[2] = dp[3];
        }
        return dp[3];
    }
}

打赏,谢谢~~

取消

感谢您的支持,我会继续努力的!

扫码支持
扫码打赏,多谢支持~

打开微信扫一扫,即可进行扫码打赏哦