文章目录
- 1. 题目
- 2. 解题
- 2.1 DP超时解
- 2.2 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