首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >LeetCode 276. 栅栏涂色(DP)

LeetCode 276. 栅栏涂色(DP)

作者头像
Michael阿明
发布2020-07-13 16:17:09
1.1K0
发布2020-07-13 16:17:09
举报

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个变量,代码略
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2020-07-03 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 1. 题目
  • 2. 解题
    • 2.1 DP超时解
      • 2.2 DP解
      领券
      问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档