[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.https://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.https://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.https://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.https://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
            if (i==opt) continue; // cannot paint same color for adjant
            dfs(idx+1, i, cost+arr[idx][i]);
        }
    }
}

时间复杂度：，每一次选择都有k-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
            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 adjant
            res = Math.min(arr[idx][i-1] + dfs(idx+1, i, dp), res);
        }
 
        return dp[idx][opt] = res;
    }
}

时间复杂度：记忆化后的时间复杂度不太好计算，大大小于；空间复杂度：，开额外空间保存记忆化结果。 

思路2 - 动态规划

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

状态转移方程为：

代码如下：

class Solution {
    public int minCost(int[][] costs) {
        int[][] dp = new int[costs.length][costs[0].length]; // [0, i] i 处涂 k的最小cost
        for (int i=0; i0].length; i++) {
            dp[0][i] = costs[0][i];
        }
 
        for (int i=1; i
            for (int k=0; k
                int res = Integer.MAX_VALUE;
                for (int j=0; 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;
    }
 
}

时间复杂度：；空间复杂度：。 

问题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];
 
    // 设置为apt
    ans+=dfs(n, i+1, r, 0, dp);
 
    if (co<=1) {
        //连续有2个那么还可以建office
        ans+=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=0
 
    dp[0][0][0] = 1; // apt
    dp[0][1][0] = 1; // cafe
    dp[0][0][1] = 1; // office
 
    for (int i=1; i
        // for rest
        for (int j=0; j<3; j++) {
            dp[i][1][0]+=dp[i-1][0][j];
        }
 
        // for office
        for (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 apt
        for (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;
}