关于leetcode:剑指-Offer-II-091粉刷房子-算法leetcode附思维导图-全部解法300题

零 题目：算法（leetcode，附思维导图 + 全副解法）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://leetcode.cn/problems/JEj789/solution/fen-shua-fang-zi-by-leetcode-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 博主简介

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