yangq's blog

观心中月,破心中贼

0%

刷算法(17)-栅栏涂色

发表于 分类于

276. 栅栏涂色

有 k 种颜色的涂料和一个包含 n 个栅栏柱的栅栏，每个栅栏柱可以用其中一种颜色进行上色。你需要给所有栅栏柱上色，并且保证其中相邻的栅栏柱 最多连续两个 颜色相同。然后，返回所有有效涂色的方案数。

屏幕快照 2019-10-20 下午12.38.43.png

解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * @param n个栅栏
 * @param k种颜色
 * @return 多少种喷法
 */
public int numWays(int n, int k) {
    if (n == 0){
        return 0;
    }else if (n == 1){
        return k;
    }else if (n == 2){
        return k * k;
    }
    int[] dp = new int[n+1];
    dp[0] = 0;
    dp[1] = k;
    dp[2] = k * k;
    for (int i = 3; i <= n; i++){
        dp[i] = dp[i-1] * (k-1) + dp[i-2] * (k-1);
    }
    return dp[n];
}

心得

  1. 需要针对n做一些特殊化处理，当n等于1只有一个栅栏时必然有k种涂法；
  2. 当n等于2时也就是有两个栅栏，共有k * k种涂法
  3. 当n大于等于3时通过动态规划实现，假设dp[i]等于有i个栅栏时的涂法，那么我们找dp[i]和dp[i-1]及之前的关系，分两种情况考虑。一种是第i个栅栏和i-1个栅栏涂的颜色不同，那必然有dp[i-1]*(k-1)种涂法。第二种情况，第i个栅栏和i-1个栅栏涂的颜色相同，那意味着i-1个栅栏和i-2个栅栏涂的颜色不同(因为最多只能有两个连续栅栏颜色相同)，也即:dp[i-2] * (k-1)，动态规划方程如下:
    1
    dp[i] = dp[i-1] * (k-1) + dp[i-2] * (k-1)
  4. 总之一句话：动态规划先梳理边界条件，再找动态规划方程！！！