欢迎来到尧图网

客户服务 关于我们

您的位置:首页 > 文旅 > 旅游 > [Leetcode刷题] - 栅栏涂漆DP类问题

[Leetcode刷题] - 栅栏涂漆DP类问题

2025/5/12 23:28:39 来源:https://blog.csdn.net/ok1382038/article/details/132022572  浏览:    关键词:[Leetcode刷题] - 栅栏涂漆DP类问题

题目描述

这一类题目通常会问给定一组房子n和一组染料k去涂漆,并且会加入限制条件比如:某种颜色只能使用1次,相相邻房子不能涂同一种颜色,或者最多不能超过连续3个房子涂想通过颜色等等,让我们列举所有可能性总和,带限制条件的排列组合类问题。

题目链接

求方案数

Leetcode 256 - Paint HouseLevel up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.icon-default.png?t=N7T8https://leetcode.com/problems/paint-house/description/

Leetcode 265 - Paint House IILevel up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.icon-default.png?t=N7T8https://leetcode.com/problems/paint-house-ii/

Leetcode 276 - Paint FenceLevel up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.icon-default.png?t=N7T8https://leetcode.com/problems/paint-fence/

盖楼问题Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.icon-default.png?t=N7T8https://leetcode.com/discuss/interview-question/1400517/UBER-OA-QUESTION-HELP-NEEDED/1104017

题目思路

问题1: 给n座房子涂漆,有k个颜色,限制条件是相邻两个房子不能涂相同颜色,求总方案数

Leetcode 256 - Paint House,Leetcode 265 - Paint House II

思路1 - 暴力搜索DFS

对于排列组合类问题,最直观的思路就是DFS暴力枚举出所有解,每一次递归我们枚举所有的颜色,跳过和当前相同颜色,然后选取剩下k-1种颜色继续计算。

代码如下:

class Solution {int min = Integer.MAX_VALUE;int[][] arr;public int minCost(int[][] costs) {arr = costs;dfs(0, -1, 0);return min;}private void dfs(int idx, int opt, int cost) {if (idx==arr.length) {min = Math.min(cost, min);return;}for (int i=0; i<arr[idx].length; i++) {if (i==opt) continue; // cannot paint same color for adjantdfs(idx+1, i, cost+arr[idx][i]);}}
}

时间复杂度:O((k-1)^N),每一次选择都有k-1个颜色可选;空间复杂度:O(1),抛去递归占用的额外栈空间。 

思路1优化 - DFS记忆化搜索

不难看出,在递归的过程中,存在着很多局部组合是重复的,我们完全可以将这些重复组合缓存起来,从而实现优化剪枝。

为了实现记忆化搜索我们需要改写思路1代码,舍弃全局最小值,而是在递归中不断更新局部最小值, 之前的思路1的代码,我们是向下递归,在到底后更新结果,这样很难缓存重复解。可以将思路1的想法改写成,向下递归,在每一层递归时计算最优解。

改写代码如下:

class Solution {int[][] arr;public int minCost(int[][] costs) {arr = costs;int[][] dp = new int[costs.length][costs[0].length+1];for (int i=0; i<costs.length; i++) {Arrays.fill(dp[i], -1);}return dfs(0, 0, dp);}private int dfs(int idx, int opt, int[][] dp) {if (idx==arr.length) {return 0;}if (dp[idx][opt]!=-1) return dp[idx][opt];int res = Integer.MAX_VALUE;for (int i=1; i<=arr[idx].length; i++) {if (i==opt) continue; //cannot paint same color for adjantres = Math.min(arr[idx][i-1] + dfs(idx+1, i, dp), res);}return dp[idx][opt] = res;}
}

时间复杂度:记忆化后的时间复杂度不太好计算,大大小于O((k-1)^N);空间复杂度:O(NK),开额外空间保存记忆化结果。 

思路2 - 动态规划

记忆化搜索其实就是自上而下的动态规划实现,我们只需要把递归逻辑转化为迭代即可。首先初始化状态 dp[i][j] 定义为从0到i个房子,在第i个房子涂j个染料时当前的最小cost。

状态转移方程为:

dp[i][j] = costs[i][j] + min_{x\epsilon {1, k}}(dp[i-1][x])

代码如下:

class Solution {public int minCost(int[][] costs) {int[][] dp = new int[costs.length][costs[0].length]; // [0, i] i 处涂 k的最小costfor (int i=0; i<costs[0].length; i++) {dp[0][i] = costs[0][i];}for (int i=1; i<costs.length; i++) {for (int k=0; k<costs[i].length; k++) {int res = Integer.MAX_VALUE;for (int j=0; j<costs[i].length; j++) {if (j==k) continue;res = Math.min(res, dp[i-1][j]);}dp[i][k] = costs[i][k] + res;}}int min = Integer.MAX_VALUE;for (int i: dp[costs.length-1]) {min = Math.min(min, i);}return min;}}

时间复杂度:O(Nk^2);空间复杂度:O(Nk)。 

问题2: 给n座房子涂漆,有k个颜色,限制条件不能给连续超过2座房子涂相同颜色,求总方案数

Leetcode 276 - Paint Fence

思路1 - 暴力搜索DFS

思路1优化 - DFS记忆化搜索

思路2 - 动态规划

问题3: 给n座房子涂漆,有k种颜色,限制条件1不能给连续超过2座房子涂相同颜色,限制条件2某种颜色最多只能用m次,求总方案数

盖楼问题

思路1 - 暴力搜索DFS

思路1优化 - DFS记忆化搜索

代码如下:

private int dfs(int n, int i, int r, int co, int[][][] dp) {if (i==n) return 1;int ans = 0;if (r==0) ans+=dfs(n, i+1, 1, 0, dp);if (dp[i][r][co]!=-1) return dp[i][r][co];// 设置为aptans+=dfs(n, i+1, r, 0, dp);if (co<=1) {//连续有2个那么还可以建officeans+=dfs(n, i+1, r, co+1, dp);}return dp[i][r][co] = ans;
}

思路2 - 动态规划

代码如下:

private int dyp(int n) {int[][][] dp = new int[n][2][3]; // n j k -> k 表示当前连续了几个如果当前为不选office, k=0dp[0][0][0] = 1; // aptdp[0][1][0] = 1; // cafedp[0][0][1] = 1; // officefor (int i=1; i<n; i++) {// for restfor (int j=0; j<3; j++) {dp[i][1][0]+=dp[i-1][0][j];}// for officefor (int j=1; j<3; j++) {dp[i][0][j]+=dp[i-1][0][j-1];dp[i][1][j]+=dp[i-1][0][j-1];}// for aptfor (int j=0; j<3; j++) {dp[i][0][0]+=dp[i-1][0][j];dp[i][1][0]+=dp[i-1][1][j];}}int sum = 0;for (int j=0; j<3; j++) {sum+=dp[n-1][0][j];sum+=dp[n-1][1][j];}return sum;
}

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

热搜词