lintcode 514. 栅栏染色 动态规划

我们有一个栅栏,它有n个柱子,现在要给柱子染色,有k种颜色可以染。
必须保证不存在超过2个相邻的柱子颜色相同,求有多少种染色方案。

样例
例 1:

输入: n=3, k=2  
输出: 6
Explanation:
          post 1,   post 2, post 3
    way1    0         0       1 
    way2    0         1       0
    way3    0         1       1
    way4    1         0       0
    way5    1         0       1
    way6    1         1       0
例 2:

输入: n=2, k=2  
输出: 4
Explanation:
          post 1,   post 2
    way1    0         0       
    way2    0         1            
    way3    1         0          
    way4    1         1       
注意事项
n和k都是非负整数

思路:最多允许两根柱子相同
第一种可能性则是在倒数第二种的基础上加上两根都是相同颜色的柱子

例如:post2后的post3和post数字均相同,且可能方案为post2的可能性*k-1(颜色数目)
          post 1,   post 2, post 3,post 4
    way1    0         0       1   	1
    way2    0         1       0		0
    way3    0         1       1		1
    way4    1         0       0		0
    way5    1         0       1		1	
    way6    1         1       0		0

第二种可能性则是在第三种的基础上加上一根不同颜色的柱子

例如:post3与post4颜色均不同,此时,post4的颜色可能性也为k-1
       post 1,   post 2, post 3,post 4
    way1    0         0       1   	0
    way2    0         1       0		1
    way3    0         1       1		0
    way4    1         0       0		1
    way5    1         0       1		0	
    way6    1         1       0		1

而简单推理就可以得到第一根柱子方案数为k,第二根柱子的方案数为kk,故后续方案数为(dp[i-1]+dp[i-2])(k-1).

class Solution {
public:
    /**
     * @param n: non-negative integer, n posts
     * @param k: non-negative integer, k colors
     * @return: an integer, the total number of ways
     */
    int numWays(int n, int k) {
        // write your code here
        if(n>2&&k==1) return 0;
        std::vector<int> result;
        result.push_back(k);
        result.push_back(pow(k,2));
        for (int i = 2; i < n; i++) {
            /* code */
            result.push_back((result[i-1]+result[i-2])*(k-1));
        }
        return result[n-1];
    }
};```

上一篇:超好用的条形码/二维码识别Python包pyzxing


下一篇:手把手用Camera2撸一个Zxing扫码