算法练习之动态规划
粉刷房间
题目描述
假如有一排房子，共 n 个，每个房子可以被粉刷成红色、蓝色或者绿色这三种颜色中的一种，你需要粉刷所有的房子并且使其相邻的两个房子颜色不能相同。
当然，因为市场上不同颜色油漆的价格不同，所以房子粉刷成不同颜色的花费成本也是不同的。每个房子粉刷成不同颜色的花费是以一个 n x 3 的正整数矩阵 costs 来表示的。
例如，costs[0][0] 表示第 0 号房子粉刷成红色的成本花费；costs[1][2] 表示第 1 号房子粉刷成绿色的花费，以此类推。
请计算出粉刷完所有房子最少的花费成本。
解题思路
- 递归暴力法
function minCost(costs: number[][]) {
const len = costs.length;
if (len === 1) {
return Math.min(...costs[0]);
}
const fn = (prevIndex: number, count: number, res: number): number => {
if (count === len) {
return res;
}
const map = new Map<number, number[]>([
[0, [1, 2]],
[1, [0, 2]],
[2, [0, 1]],
]);
const arr = map.get(prevIndex)!;
return Math.min(...arr.map((v) => fn(v, count + 1, res + costs[count][v])));
};
const r = fn(0, 1, costs[0][0]);
const g = fn(1, 1, costs[0][1]);
const b = fn(2, 1, costs[0][2]);
return Math.min(r, g, b);
}
不需要思考任何算法的一种方式, 直接递归计算出所有可能, 但是中间会包含很多重复计算, 执行 LeetCode 测试时会超时. 所以需要进一步思考最优解.
- 动态规划
function minCost(costs: number[][]) {
let [r, b, g] = costs[0];
for (let i = 1; i < costs.length; ++i) {
[r, b, g] = [
Math.min(b, g) + costs[i][0],
Math.min(r, g) + costs[i][1],
Math.min(r, b) + costs[i][2],
];
}
return Math.min(r, g, b);
}
大致思路:
- 定义变量 r、b、g 分别表示粉刷至某一间房时红色、蓝色、绿色所需粉刷的最小花费
- let [r, b, g] = costs[0] 即表示粉刷第一间时的最小花费
- 从第二间房开始遍历, 第二间房可粉刷三种任意颜色, 但限制条件为粉刷红色时, 前一间房子的粉刷只能为绿色或蓝色, 依次类推, 得到
[r, b, g] = [
Math.min(b, g) + costs[i][0],
Math.min(r, g) + costs[i][1],
Math.min(r, b) + costs[i][2],
];
这里使用了 ES6 的数组解构, 类似于对象解构, 赋值语句左侧为粉刷到第 i 间房对应某一种颜色时的总最小花费, 右侧 Math.min(b, g) 表示粉刷到上一间房使用蓝色或绿色时的最小花费, costs[i][0] 表示粉刷第 i间房时使用红色的情况, 然后继续赋值给 r, 后续依次类推. 当循环结束时, 最后得到的 r、b、g 即为最后一间房子粉刷某一种情况的总花费, 最后返回最小值即可.