514. 栅栏染色

Posted on

Description

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

Example

n = 3, k = 2, return 6

1
2
3
4
5
6
7
      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

Solution

这类型的题动态规划是比较适合的。

先以n=3来分析。第一根可选颜色是k,第二根也是k。用一个record[]来表示，record[0]表示第一根柱子的可选方案，record[1]表示前两根柱子的可选方案，就是record[1] = k * k.

到了第三根的时候就要分情况来讨论 ,前三根的可选方案有：

1) 第一根与第二根同色,三根的可选方案为：k (k-1).
2) 第一根与第二根不同色,则第三根与第一根就没有关系了，三根的可选方案为：k k * (k-1).

所以设 i = 3 的时候，可以得到状态转移方程：

1
record[i] = record[i-2] * ( k-1 ) + record[i-1] * ( k-1 );

然后 record[0] = k, record[1] = k * k.

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

当然，其实我们要的就是最后一个值，所以空间上也是可以优化的，改用两个变量来保存 i, i-1 ,i-2 三个值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
 * @param n: non-negative integer, n posts
 * @param k: non-negative integer, k colors
 * @return: an integer, the total number of ways
 */
const numWays = function (n, k) {
        if (n === 0) {
            return 0;
        }
        if (n === 1) {
            return k;
        }
        if (n === 2) {
            return k*k;
        } else {
           let llval = k,val;
           let lval = k * k;
           for (var i = 2; i < n ; i++){
               val = (lval + llval) * (k-1);
               llval = lval;
               lval = val;
           }
           return val;
        }
        
}