📃 题目描述

题目链接：

• 剑指 Offer II 091. 粉刷房子 - 力扣（LeetCode） (opens new window)
• 256. 粉刷房子 - 力扣（LeetCode） (opens new window)

🔔 解题思路

二维数组 dp[i][3]

• dp[i][0]: 将下标为 i 的房子粉刷成 红色 (costs[i][0]) 需要的花费
• dp[i][1]: 将下标为 i 的房子粉刷成 蓝色 (costs[i][1]) 需要的花费
• dp[i][2]: 将下标为 i 的房子粉刷成 绿色 (costs[i][2]) 需要的花费

class Solution {
    public int minCost(int[][] costs) {
        if (costs == null || costs.length == 0) {
            return 0;
        }

        if (costs.length == 1) {
            return Math.min(costs[0][0], Math.min(costs[0][1], costs[0][2]));
        }

        int n = costs.length;
        int[][] dp = new int[n][3];

        // base case
        dp[0][0] = costs[0][0];
        dp[0][1] = costs[0][1];
        dp[0][2] = costs[0][2];

        for (int i = 1; i < n; i ++) {
            dp[i][0] = Math.min(dp[i - 1][1], dp[i - 1][2]) + costs[i][0];
            dp[i][1] = Math.min(dp[i - 1][0], dp[i - 1][2]) + costs[i][1];
            dp[i][2] = Math.min(dp[i - 1][0], dp[i - 1][1]) + costs[i][2];
        }

        return Math.min(dp[n - 1][0], Math.min(dp[n - 1][1], dp[n - 1][2]));
    }
}

空间压缩：

class Solution {
    public int minCost(int[][] costs) {
        if (costs == null || costs.length == 0) {
            return 0;
        }

        if (costs.length == 1) {
            return Math.min(costs[0][0], Math.min(costs[0][1], costs[0][2]));
        }

        int n = costs.length;
        int[] dp = new int[3];

        // base case
        dp[0] = costs[0][0];
        dp[1] = costs[0][1];
        dp[2] = costs[0][2];

        for (int i = 1; i < n; i ++) {
            // 使用临时变量存储 dp[0] 和 dp[1]，因为计算 dp[2] 的时候 dp[0] 和 dp[1] 已经发生更新了
            int temp0 = dp[0];
            int temp1 = dp[1];

            dp[0] = Math.min(dp[1], dp[2]) + costs[i][0];
            dp[1] = Math.min(temp0, dp[2]) + costs[i][1];
            dp[2] = Math.min(temp0, temp1) + costs[i][2];
        }

        return Math.min(dp[0], Math.min(dp[1], dp[2]));
    }
}

💥 复杂度分析

• 空间复杂度：
• 时间复杂度：