六虎

【动态规划】粉刷房子问题

【动态规划】粉刷房子问题

作者：

努力奋起的女码农

在

携手创作，一起生长！这是我参与「日新计划 8 月更文挑战」的第31天，点击检查活动详情

（1）粉刷房子

LeetCode 256

题干分析

这个标题说的是，你要用红/蓝/绿三种不同的色彩去粉刷 n 个房子，一个房子只能刷成一种色彩，而且相邻的房子不能粉刷相同的色彩。

现在给你一个 nx3 的费用矩阵，表明每个房子刷成红/蓝/绿 3 种色彩对应的费用。你要计算出，粉刷这 n 个房子的最小费用。注意，矩阵中的费用都为正整数。

# 比如说，给你的费用矩阵 a 是：
8 2 4
5 7 3
9 1 6
4 1 9
对于这个比如，你要将 0 号房子刷成蓝色，将 1 号房子刷成绿色，将 2 号房子刷成蓝色，将 3 号房子刷成赤色。
最终得到的最小费用是 2 + 3 + 1 + 4 = 10。

思路解法

再来看清下题意：

【动态规划】粉刷房子问题

动态规划解法：

  1. 找到 “状况” 和 挑选：
    • 状况：初始 d(0, 0) = a(0, 0)、d(0, 1) = a(0, 1) 、d(0, 2) = a(0, 2)
    • 挑选：挑选粉刷费用最小的，相邻的房子不能粉刷相同的色彩。
  2. dp 数组界说： d(i,j) 表明粉刷 0~i号房子，而且第 i号房子运用第 j 种色彩的最小费用。
    • j 的取值只有 0/1/2 三种， 别离表明红/蓝/绿 3种色彩。
  3. 状况之间的联系：
    • d(i,0) = min(d(i-1, 1), d(i-1, 2)) + a(i, 0)
    • d(i,1) = min(d(i-1, 0), d(i-1, 2)) + a(i, 1)
    • d(i,2) = min(d(i-1, 0), d(i-1, 1)) + a(i, 2)
public class LeetCode_256 {
    // Time: O(n), Space: O(n)
    public int minCost(int[][] costs) {
        if (costs == null || costs.length == 0) return 0;
        int n = costs.length;
        int[][] d = new int[n][3];
        d[0][0] = costs[0][0];
        d[0][1] = costs[0][1];
        d[0][2] = costs[0][2];
        for (int i = 1; i < n; ++i) {
            d[i][0] = Math.min(d[i-1][1], d[i-1][2]) + costs[i][0];
            d[i][1] = Math.min(d[i-1][0], d[i-1][2]) + costs[i][1];
            d[i][2] = Math.min(d[i-1][0], d[i-1][1]) + costs[i][2];
        }
        return min(d[n-1][0], d[n-1][1], d[n-1][2]);
    }
    private int min(int a, int b, int c) {
        return Math.min(a, Math.min(b, c));
    }
}

优化一：统一初始计算到循环中

  • d(i, j) 新界说： 表明粉刷 0~i-1 号房子，而且第 i-1 号房子运用第 j 种色彩的最小费用。
public class LeetCode_256 {
    // Time: O(n), Space: O(n)
    public int minCostOpt(int[][] costs) {
        if (costs == null || costs.length == 0) return 0;
        int n = costs.length;
        int[][] d = new int[n+1][3];
        for (int i = 1; i <= n; ++i) {
            d[i][0] = Math.min(d[i-1][1], d[i-1][2]) + costs[i-1][0];
            d[i][1] = Math.min(d[i-1][0], d[i-1][2]) + costs[i-1][1];
            d[i][2] = Math.min(d[i-1][0], d[i-1][1]) + costs[i-1][2];
        }
        return min(d[n][0], d[n][1], d[n][2]);
    }
}

优化二：空间复杂度优化到常量

  • 用暂时变量保存上一个状况
public class LeetCode_256 {
    // Time: O(n), Space: O(1)
    public int minCostO1(int[][] costs) {
        if (costs == null || costs.length == 0) return 0;
        int n = costs.length;
        int preR = 0, preB = 0, preG = 0;
        for (int i = 1; i <= n; ++i) {
            int curR = Math.min(preB, preG) + costs[i-1][0];
            int curB = Math.min(preR, preG) + costs[i-1][1];
            int curG = Math.min(preR, preB) + costs[i-1][2];
            preR = curR;
            preB = curB;
            preG = curG;
        }
        return min(preR, preB, preG);
    }
}

（2）K 种色彩粉刷房子

LeetCode 265

题干分析

这个标题说的是，你要用 k 种不同的色彩去粉刷 n 个房子，一个房子只能刷成一种色彩，而且相邻的房子不能粉刷相同的色彩。

现在给你一个 nxk 的费用矩阵，表明每个房子刷成 k 种色彩对应的费用。你要计算出，粉刷这 n 个房子的最小费用。注意，矩阵中的费用都为正整数。

# 比如说，给你的费用矩阵 a 是：
8 2 4
5 7 3
9 1 6
4 1 9

# 对于这个比如，你要将 0 号房子刷成 1 号色彩，将 1 号房子刷成 2 号色彩，将 2 号房子刷成 1 号色彩，将 3 号房子刷成 0 号色彩。

# 最终得到的最小费用是 2 + 3 + 1 + 4 = 10。

思路解法

再来看清下题意：

【动态规划】粉刷房子问题

动态规划解法：

  1. 找到 “状况” 和 挑选：

    • 挑选：挑选粉刷费用最小的，相邻的房子不能粉刷相同的色彩。

  2. dp 数组界说： d(i, j) 表明粉刷 0~i-1 号房子，而且第 i-1 号房子运用第 j 种色彩的最小费用。

  3. 状况之间的联系： d(i,j) = min(d(i-1, c)) + a(i-1, j)

    • c: 0 -> k-1, c != j
    • i: 1 -> n
    • j: 0 -> k-1
    • 最终结果求： min(d(n, i)), i: 0 -> k-1 
public class LeetCode_265 {
    // Time: O(n*k^2), Space: O(n*k)
    public int minCost(int[][] costs) {
        if (costs == null || costs.length == 0) return 0;
        int n = costs.length, k = costs[0].length;
        if (k == 1) return costs[0][0];
        int[][] d = new int[n + 1][k];
        for (int i = 1; i <= n; ++i) {
            for (int j = 0; j < k; ++j) {
                int min = Integer.MAX_VALUE;
                for (int c = 0; c < k; ++c) {
                    if (c != j) min = Math.min(min, d[i - 1][c]);
                }
                d[i][j] = min + costs[i - 1][j];
            }
        }
        int min = d[n][0];
        for (int i = 1; i < k; ++i) {
            min = Math.min(min, d[n][i]);
        }
        return min;
    }
}

优化一：

【动态规划】粉刷房子问题

public class LeetCode_265 {
    // Time: O(n*k), Space: O(n*k)
    public int minCostOpt(int[][] costs) {
        if (costs == null || costs.length == 0) return 0;
        int n = costs.length, k = costs[0].length;
        if (k == 1) return costs[0][0];
        int[][] d = new int[n + 1][k];
        int preIdx1 = 0, preIdx2 = 1;
        for (int i = 1; i <= n; ++i) {
            int idx1 = -1, idx2 = -1;
            for (int j = 0; j < k; ++j) {
                if (j != preIdx1) d[i][j] = d[i - 1][preIdx1] + costs[i - 1][j];
                else d[i][j] = d[i - 1][preIdx2] + costs[i - 1][j];
                if (idx1 < 0 || d[i][j] < d[i][idx1]) {
                    idx2 = idx1;
                    idx1 = j;
                } else if (idx2 < 0 || d[i][j] < d[i][idx2]) {
                    idx2 = j;
                }
            }
            preIdx1 = idx1;
            preIdx2 = idx2;
        }
        int min = d[n][0];
        for (int i = 1; i < k; ++i) {
            min = Math.min(min, d[n][i]);
        }
        return min;
    }
}

优化三：空间复杂度优化到常量

  • 用暂时变量保存上一个状况
public class LeetCode_265 {
    // Time: O(n*k), Space: O(1)
    public int minCostO1(int[][] costs) {
        if (costs == null || costs.length == 0) return 0;
        int n = costs.length, k = costs[0].length;
        if (k == 1) return costs[0][0];
        int preMin1 = 0, preMin2 = 0;
        int preIdx1 = 0;
        for (int i = 1; i <= n; ++i) {
            int min1 = Integer.MAX_VALUE, min2 = Integer.MAX_VALUE;
            int idx1 = -1;
            for (int j = 0; j < k; ++j) {
                int cost;
                if (j != preIdx1) cost = preMin1 + costs[i - 1][j];
                else cost = preMin2 + costs[i - 1][j];
                if (cost < min1) {
                    min2 = min1;
                    min1 = cost;
                    idx1 = j;
                } else if (cost < min2) {
                    min2 = cost;
                }
            }
            preMin1 = min1;
            preMin2 = min2;
            preIdx1 = idx1;
        }
        return preMin1;
    }
}

更多文章