动态规划是一种思维逻辑, 并没有固定的"公式"
爬楼梯问题
题目描述
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意: 给定 n 是一个正整数。
示例
示例 1：
输入: 2
输出: 2
解释： 有两种方法可以爬到楼顶
- 1 阶 + 1 阶
- 2 阶
示例 2：
输入: 3
输出: 3
解释: 有三种方法可以爬到楼顶。
- 1 阶 + 1 阶 + 1 阶
- 1 阶 + 2 阶
- 2 阶 + 1 阶
思路
1. 递归
思路
记
f(n) 的结果是 n 个台阶有多少种不同方法到楼顶易知
f(1) = 1, f(2) = 2因为只有
n-1 和 n-2 能够到达 n所以有
f(n) = f(n-1) + f(n-2), f(n-1) = f(n-2) + f(n-3)代码实现
// 递归
const recursive = (n) => {
if (n === 1) {
return 1
}
if (n === 2) {
return 2
}
return recursive(n - 1) + recursive(n - 2)
}优化点
使用递归来解决这个问题, 再 OJ 中会直接超时
因为有大量的重复计算, 如下图红色点
2. 记忆化搜索
解决时间效率上的问题, 最直接的思路就是空间换时间
所谓记忆化搜索就是缓存已计算出的结果, 避免重复计算
代码实现
// 记忆化搜索
const f = []
const memorize = (n) => {
if (n === 1) {
return 1
}
if (n === 2) {
return 2
}
// 判断 f(n) 是否存在, 如不存在, 则计算; 如存在, 则直接返回
return f[n] ? f[n] : recursive(n - 1) + recursive(n - 2)
}3.动态规划
代码实现
// 动态规划
const dp = (n) => {
// 初始化状态数组
let f = [1, 2]
// 更新每一层楼梯对应的结果
for (let i = 2; i < n; i++) {
f[i] = f[i - 1] + f[i - 2]
}
// 返回结果
return f[n - 1]
}找硬币问题
提示：最值问题是动态规划的常见对口题型，见到最值问题，应该想到动态规划
题目描述
给定不同面额的硬币
coins和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。示例
示例1: 输入:
coins = [1, 2, 5], amount = 11输出:
3解释:
11 = 5 + 5 + 1示例2: 输入:
coins = [2], amount = 3输出:
-1思路
代码实现
/**
* @param {number[]} coins
* @param {number} amount
* @return {number}
*/
var coinChange = function (coins, amount) {
// 保存每个 amount 的最小硬币个数
const f = []
// 已知条件
f[0] = 0
// 遍历 [1, amount] 之间总额
for (let i = 1; i <= amount; i++) {
f[i] = Infinity
// 遍历硬币数值, 找出可以用的面值
for (let j = 0; j < coins.length; j++) {
// 当总额大于当前硬币面值, 才有可能是最小值
if (i - coins[j] >= 0) {
f[i] = Math.min(f[i], f[i - coins[j]] + 1)
}
}
}
if (f[amount] === Infinity) {
return -1
}
return f[amount]
};思考
记忆化搜索和动态规划的区别
- 记忆化搜索可以理解为优化后的递归, 递归思想是一个自顶向下的过程
- 动态规划, 是一个自底向上的过程, 要求我们在已知的角度, 推导出已知和未知的关系
动态规划和分治思想
分治思想: 把一个问题分解为相互独立的子问题, 逐个解决子问题后, 再组合子问题的答案, 就得到了问题的最终解
- 分治思想的各个子问题之间是独立的
- 动态规划的思想划分的子问题是相互依赖、相互影响的
什么时候应该使用动态规划
- 最优子结构
- 重叠子问题