零 标题：算法（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 历史文章 - 总览
刷题进度 - LeetCode：545 / 2678 、《剑指offer》：66 / 66
2 博主简介
码农三少 ，一个致力于编写 极简、但齐全题解（算法） 的博主。
专注于 一题多解、结构化思维 ，欢迎一起刷穿 LeetCode ~
网友评论