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. 总之一句话:动态规划先梳理边界条件,再找动态规划方程!!!