LeetCode刷题【276】栅栏涂色

有 k 种颜色的涂料和一个包含 n 个栅栏柱的栅栏，请你按下述规则为栅栏设计涂色方案：

• 每个栅栏柱可以用其中 一种 颜色进行上色。
• 相邻的栅栏柱 最多连续两个 颜色相同。

给你两个整数 k 和 n ，返回所有有效的涂色 方案数 。

 

示例 1：

输入：n = 3, k = 2
输出：6
解释：所有的可能涂色方案如上图所示。注意，全涂红或者全涂绿的方案属于无效方案，因为相邻的栅栏柱 最多连续两个 颜色相同。

示例 2：

输入：n = 1, k = 1
输出：1

示例 3：

输入：n = 7, k = 2
输出：42

 

提示：

• 1 <= n <= 50
• 1 <= k <= 105
• 题目数据保证：对于输入的 n 和 k ，其答案在范围 [0, 231 - 1] 内

题解

首先我们知道，当只有一根栅栏的时候，有k种选择，而后续的情况分是否和前一根栅栏相同两种情况

栅栏编号	和前一个同色	不同色	总方案数
2	k	k*（k-1）	k+k*(k-1)
3	k*（k-1）	(k+k*(k-1))*(k-1)	......

第n根栅栏和前一根（n-1）同色的时候，n-1位置和n-2位置必然不能同色，及直接取n-1位置时候不同色的值。

而当前栅栏和前一个栅栏不同色的话，则当前栅栏有k-1种选择，不论n-1和n-2位置是否相同

状态转移方程

 dp[n][0] = dp[n − 1][1];
 dp[n][1] = (dp[n − 1][0] + dp[n − 1][1]) ∗ (k − 1);

代码，下标1代表和前一个相同颜色，下标2代表和前一个不同颜色，下标3代表到本位置栅栏有多少种情况总和，

class Solution {
    public int numWays(int n, int k) {
        if (n==1){
            return k;
        }
        int[][] dp = new int[n][3];
        dp[0][2] = k;
        dp[1][0] = k;
        dp[1][1] = k * ( k - 1 );
        dp[1][2] = dp[1][0] + dp[1][1];
        int i = 2;
        while (i < n){
            dp[i][0] = dp[i-1][1];
            dp[i][1] = dp[i-1][2] * ( k - 1 );
            dp[i][2] = dp[i][0] + dp[i][1];
            i++;
        }
        return dp[n-1][2];
    }
}

当然因为每个阶段的总和是直接由0下标和1下标求和而得，这个2下标的位置可以省略。再和之前一样，把长度为n的dp数组重新压缩转换成长度为2的数组，那么这边代码就可以优化成这样

class Solution {
    public int numWays(int n, int k) {
        if (n==1){
            return k;
        }
        int[][] dp = new int[2][2];
        dp[0][0] = k;
        dp[0][1] = k * ( k - 1 );
        int count = 2;
        int cur = 1;
        int before = 0;
        while (count < n){
            dp[cur][0] = dp[before][1];
            dp[cur][1] = (dp[before][0] + dp[before][1]) * ( k - 1 );
            count++;
            if (cur == 1){
                cur = 0;
                before = 1;
            }else {
                cur = 1;
                before = 0;
            }
        }
        return dp[before][0]+dp[before][1];
    }
}

重新回顾下

在第一份代码中

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

可以转换为

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

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

所以

class Solution {
    public int numWays(int n, int k) {
        if (n==1){
            return k;
        }
        int[] dp = new int[n];
        dp[0] = k;
        dp[1] = k * k;
        int idx = 2;
        while (idx<n){
            dp[idx] = (dp[idx-2] + dp[idx-1]) * ( k - 1);
            idx++;
        }
        return dp[--idx];
    }
}

这个代码一样可以把length为n的数组改为length为2的数组，这个就省去不写了。