关于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 ~