零 标题：算法（********，附思维导图 + 全部解法）300题之（剑指 Offer II 091）粉刷房子

一 题目描述

二 解法总览（思维导图）

三 全部解法

1 方案1

1)代码：

// 方案1 “自己。动态规划法”。
// 用时：10：47 - 10：57。
// 想法：
// 1）“题干有最字眼，优先考虑动态规划”。
// 2）状态定义：dp[i][j] —— 以房子i结尾 且 其刷成颜色j 的最低价格。
// 3）状态转移：dp[i][j] = Math.min(dp[i][j], dp[i - 1][k] + costs[i][j]);
// i的范围：[1, l - 1]，j的范围：[0, 2]，j与k的关系 j !== k 。

// 思路：
// 1）状态初始化：l = costs.length;
// dp = new Array(l).fill(0).map(v => new Array(3).fill(Number.POSITIVE_INFINITY));
// dp[0] = costs[0]; 。
// 2）核心：状态转移：dp[i][j] = Math.min(dp[i][j], dp[i - 1][k] + costs[i][j]);
// i的范围：[1, l - 1]，j的范围：[0, 2]，j与k的关系 j !== k 。
// 3）返回结果：Math.min(...dp[l - 1]); 。
var minCost = function(costs) {
    // 1）状态初始化：l = costs.length;
    // dp = new Array(l).fill(0).map(v => new Array(3).fill(Number.POSITIVE_INFINITY));
    // dp[0] = costs[0]; 。
    const l = costs.length;
    let dp = new Array(l).fill(0).map(v => new Array(3).fill(Number.POSITIVE_INFINITY));
    dp[0] = costs[0];

    // 2）核心：状态转移：dp[i][j] = Math.min(dp[i][j], dp[i - 1][k] + costs[i][j]);
    // i的范围：[1, l - 1]，j的范围：[0, 2]，j与k的关系 j !== k 。
    for (let i = 1; i < l; i++) {
        // 注：如下6行代码等价于如下
        // for (let j = 0; j <= 2; j++) {
        //     for (let k = 0; k <= 2; k++) {
        //         if (j !== k) {
        //             dp[i][j] = Math.min(dp[i][j], dp[i - 1][k] + costs[i][j]);
        //         }
        //     }
        // }
        dp[i][0] = Math.min(dp[i][0], dp[i - 1][1] + costs[i][0]);
        dp[i][0] = Math.min(dp[i][0], dp[i - 1][2] + costs[i][0]);
        dp[i][1] = Math.min(dp[i][1], dp[i - 1][0] + costs[i][1]);
        dp[i][1] = Math.min(dp[i][1], dp[i - 1][2] + costs[i][1]);
        dp[i][2] = Math.min(dp[i][2], dp[i - 1][0] + costs[i][2]);
        dp[i][2] = Math.min(dp[i][2], dp[i - 1][1] + costs[i][2]);
    }

    // 3）返回结果：Math.min(...dp[l - 1]); 。
    return Math.min(...dp[l - 1]);
};

2 方案2

1)代码：

// 方案2 “官方。动态规划 - 滚动数组法”。
// 参考：
// 1）https://********.cn/problems/JEj789/solution/fen-shua-fang-zi-by-********-solution-q0kh/

// 想法：
// 0）“题干有最字眼，优先考虑动态规划”。
// 1）状态定义：dp[i][j] —— 以房子i结尾 且 其刷成颜色j 的最低价格。
// 2）状态转移方程：dp[i][j] = min(dp[i − 1][(j + 1) % 3],dp[i − 1][(j + 2) % 3]) + costs[i][j]，
// 1 ≤ i < n 和 0 ≤ j < 3。

// 思路：
// 1）状态初始化：l =costs.length; dp = costs[0]; 。
// 2）核心：状态转移 —— dp[i][j] = min(dp[i − 1][(j + 1) % 3],dp[i − 1][(j + 2) % 3]) + costs[i][j]，
// 1 ≤ i < n 和 0 ≤ j < 3。
// 3）返回结果：Math.min(...dp); 。
var minCost = function(costs) {
    // 1）状态初始化：l =costs.length; dp = costs[0]; 。
    const l =costs.length;
    let dp = costs[0];

    // 2）核心：状态转移 —— dp[i][j] = min(dp[i − 1][(j + 1) % 3],dp[i − 1][(j + 2) % 3]) + costs[i][j]，
    // 1 ≤ i < n 和 0 ≤ j < 3。
    for (let i = 1; i < l; i++) {
        dpNew = new Array(3).fill(0);
        for (let j = 0; j < 3; j++) {
            dpNew[j] = Math.min(dp[(j + 1) % 3], dp[(j + 2) % 3]) + costs[i][j];
        }
        dp = dpNew;
    }

    // 3）返回结果：Math.min(...dp); 。
    return Math.min(...dp);
};

四 资源分享 & 更多

1 历史文章 - 总览

2 博主简介

码农三少 ，一个致力于编写 极简、但齐全题解（算法） 的博主。
专注于 一题多解、结构化思维 ，欢迎一起刷穿 ******** ~