lintcode514 栅栏染色

栅栏染色

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

注意事项

n和k都是非负整数

您在真实的面试中是否遇到过这个题？

Yes

样例

n = 3, k = 2, return 6

      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

动态规划

 1 class Solution {
 2 public:
 3     /*
 4      * @param n: non-negative integer, n posts
 5      * @param k: non-negative integer, k colors
 6      * @return: an integer, the total number of ways
 7      */
 8     int numWays(int n, int k) {
 9         if (n == 0) {
10             return 0;
11         }
12         if (n == 1) {
13             return k;
14         }
15         if (n == 2) {
16             return k*k;
17         } else {
18             int * m = new int[n];
19             m[0] = k;
20             m[1] = k*k;
21             for (int i = 2; i < n; i++) {
22                 m[i] = m[i-1] * (k-1) + m[i-2] * (k-1);
23             }
24             return m[n-1];
25         }
26     }
27 };