「图解大厂面试高频算法题」链表专题-栅栏涂色

PS: 本文为「图解大厂面试高频算法题」专题，主旨是根据“二八法则”的原理，以付出20%的时间成本，获得80%的刷题的收益，让那些想进互联网大厂的人少走些弯路。

PS: 欢迎关注我获取更多大厂面试总结。

原题链接: https://leetcode-cn.com/problems/paint-fence/

题目介绍

题目解答

首先寻找子问题

题目的原问题是求解用K种颜色粉刷从第0到第N个围栏共有几种方案，这个问题可以拆成如下N个子问题

• 用K种颜色粉刷第0个围栏共有几种方案
• 用K种颜色粉刷从第0到第1个围栏共有几种方案
• … …
• 用K种颜色粉刷从第0到第N-1个围栏共有几种方案
• 用K种颜色粉刷从第0到第N个围栏共有几种方案
  
  注意这题有一个限制就是相邻的栅栏最多连续两个颜色相同，所以小粉刷匠每刷一个围栏的时候，他需要思考这个房子要刷哪种颜色，刷第1种颜色？刷第2种颜色？刷第K种颜色？这样每一个子问题又可以继续拆解变成如下K*N个子问题
  
• 用K种颜色粉刷从第0到第0个围栏共有几种方案
  • 给第0个围栏刷第1种颜色时，粉刷从第0到第0个围栏共有几种方案？
  • 给第0个围栏刷第2种颜色时，粉刷从第0到第0个围栏共有几种方案？
  • … …
  • 给第0个围栏刷第K种颜色时，粉刷从第0到第0个围栏共有几种方案？
• 用K种颜色粉刷从第0到第1个围栏共有几种方案
  • 给第1个围栏刷第1种颜色时，粉刷从第0到第1个围栏共有几种方案？
  • 给第1个围栏刷第2种颜色时，粉刷从第0到第1个围栏共有几种方案？
  • … …
  • 给第1个围栏刷第K种颜色时，粉刷从第0到第1个围栏共有几种方案？
• … …
• 用K种颜色粉刷从第0到第N-1个围栏共有几种方案
  • 给第N-1个围栏刷第1种颜色时，粉刷从第0到第N-1个围栏共有几种方案？
  • 给第N-1个围栏刷第2种颜色时，粉刷从第0到第N-1个围栏共有几种方案？
  • … …
  • 给第N-1个围栏刷第K种颜色时，粉刷从第0到第N-1个围栏共有几种方案？
• 用K种颜色粉刷从第0到第N个围栏共有几种方案
  • 给第N个围栏刷第1种颜色时，粉刷从第0到第N个围栏共有几种方案？
  • 给第N个围栏刷第2种颜色时，粉刷从第0到第N个围栏共有几种方案？
  • … …
  • 给第N个围栏刷第K种颜色时，粉刷从第0到第N个围栏共有几种方案？

确定状态转移方程

子问题已经确定出来了，那么如果我们知道了子问题用K种颜色粉刷从第0到第N-1个围栏共有几种方案，那么我们如何根据这个子问题来算出原问题用K种颜色粉刷从第0到第N个围栏共有几种方案呢？

粉刷匠为了计算出方案个数，自学了编程然后搞了K个数组color1、color2 … colorK，color1[n]表示用K种颜色粉刷从第0到第N个围栏共有几种方案，且第N个围栏粉刷为第1种颜色。

color2[n] … colorK[n]亦然，粉刷匠每到达一个围栏的时候，都会去更新color1[n]、color2 [n] … colorK[n]，当粉刷匠来到了第N个围栏时心里可能这么想：

• 我要把第N个围栏刷为第K种颜色
  • 粉刷匠决定把第N个围栏刷为第K种颜色，并记录下当前第N个围栏刷为第K种颜色共有几种方案colorK[n] = (color1[n-1]+ … + colorK-1[n-1]) + (color1[n-2] + … + colorK-1[n-2] )。
  • 解释: 第N个围栏刷为第K种颜色时，用K种颜色粉刷从第0到第N个围栏共有几种方案数量等于第N-2个围栏不能是第K种颜色的数量加上第N-1个围栏不能是第K种颜色的数量，如下图所示。
    

我们又注意到无论第N个围栏是哪种颜色，用K种颜色粉刷从第0到第N个围栏的方法数量其实都是相等的，跟第N个围栏是哪种颜色无关，也就是说

color1[n] == color2[n] == … == colorK[n]

所以上述用K种颜色粉刷从第0到第N个围栏共有几种方案，其第N个围栏粉刷为第K种颜色

colorK[n] = (color1[n-1]+ … + colorK-1[n-1]) + (color1[n-2] + … + colorK-1[n-2] )

可以化简为

color[n] = color[n-1](K-1) + color[n-2](K-1)

其中color[n]表示用K种颜色粉刷从第0到第N个围栏共有几种方案。
因此状态转移方程如下

dp[n] = dp[n-1](K-1) + dp[n-2](K-1)

其中dp有两个初始状态

dp[0] = k，dp[1] = k*k

方法一：一维动态规划

代码实现

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;
        for (int i = 2; i < dp.length; i++) {
            dp[i] = (k-1) * (dp[i-1] + dp[i-2]);
        }
        return dp[n-1];
    }
}

复杂度分析

• 时间复杂度:O(N)
• 空间复杂度:O(N)

方法二：动态规划优化版

在方法一中，dp[i]的状态总是依赖于dp[i-1]与dp[i-2]，可以用两个变量来dp1和dp2来代替dp数组。

代码实现

class Solution {
    public int numWays(int n, int k) {
        if (n == 1) {
            return k;
        }
        int dp2 = k;
        int dp1 = k*k;
        for (int i = 2; i < n; i++) {
            int dp1t = dp1;
            dp1 = (k-1) * (dp1 + dp2);
            dp2 = dp1t;
        }
        return dp1;
    }
}

复杂度分析

• 时间复杂度:O(N)
• 空间复杂度:O(1)