python数据结构（栅栏涂色DP）

1. 题目

有 k 种颜色的涂料和一个包含 n 个栅栏柱的栅栏，每个栅栏柱可以用其中一种颜色进行上色。

你需要给所有栅栏柱上色，并且保证其中相邻的栅栏柱 最多连续两个 颜色相同。然后，返回所有有效涂色的方案数。

注意:
n 和 k 均为非负的整数。

示例: 输入: n = 3，k = 2 输出: 6 解析: 用 c1 表示颜色 1，c2 表示颜色 2，所有可能的涂色方案有: 柱 1 柱 2 柱 3 ----- ----- ----- ----- 1 c1     c1     c2 2 c1     c2     c1 3 c1     c2     c2 4 c2     c1     c1 5 c2     c1     c2 6 c2     c2     c1 

2. 解题

2.1 DP超时解

• 超时例子， 64 / 79 个通过测试用例

2 n 46340 k，时间复杂度O(nk^2) 

class Solution { public: int numWays(int n, int k) { if(n==0 || k==0) return 0; int conti = 2;//最多连续的次数 vector<vector<vector<int>>> dp(n,vector<vector<int>>(k,vector<int>(conti+1,0))); //dp[i][c][conti]表示遍历完i栅栏，其颜色为c，c颜色连续了conti次的方案数 int i, c, nc, ct; for(c = 0; c < k; ++c) dp[0][c][1] = 1; for(i = 1; i < n; ++i) { for(c = 0; c < k; ++c) { for(ct = 1; ct <= conti; ++ct) for(nc = 0; nc < k; ++nc) { if(c == nc && ct+1 <= conti) dp[i][nc][ct+1] += dp[i-1][c][ct]; else if(c != nc) dp[i][nc][1] += dp[i-1][c][ct]; } } } int sum = 0; for(c = 0; c < k; ++c) for(ct = 1; ct <= conti; ++ct) sum += dp[n-1][c][ct]; return sum; } }; 

2.2 DP解

• 前两个颜色一样，dp[i-2] 的方案数，dp[i-2]*1*(k-1)，i 跟他们必须不一样（k-1种选择）
• 前两个颜色不一样，i-2 占了一种颜色， i-1 占了一种颜色，i 还能选择 k-1 种颜色（可以跟 i-2 一样），方案数为 dp[i-1]*(k-1)

class Solution { public: int numWays(int n, int k) { if(n==0 || k==0) return 0; vector<int> dp(n,0); //dp[i]表示遍历完i栅栏的方案数 if(n>=1) dp[0] = k; if(n>=2) dp[1] = k*k; for(int i = 2; i < n; ++i) { dp[i] = dp[i-1]*(k-1)+dp[i-2]*(k-1); } return dp[n-1]; } }; 

0 ms 6.2 MB

class Solution: # py3
    def numWays(self, n: int, k: int) -> int: if n==0 or k==0: return 0 dp = [0]*n if n >= 1: dp[0] = k if n >= 2: dp[1] = k**2 for i in range(2, n): dp[i] = (dp[i-1]+dp[i-2])*(k-1) return dp[n-1] 

36 ms 13.6 MB

• 状态可以进一步压缩成3个变量，代码略

本文地址：https://blog.csdn.net/qq_21201267/article/details/107103497