当前位置： 移动技术网 > IT编程>脚本编程>Python > LeetCode 276. 栅栏涂色（DP）

LeetCode 276. 栅栏涂色（DP）

2020年07月04日  | 移动技术网IT编程  | 我要评论

文章目录

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

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/paint-fence
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

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个变量，代码略

长按或扫码关注我的公众号，一起加油、一起学习进步！
Michael阿明

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

您可能感兴趣的文章:

如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网