动态规划
动态规划方法论
动态规划是一种思想，所谓思想，就是非常好用，好用到爆的套路。我们学习一种思想，重要的是建立起对它的感性认知，而不是反复咀嚼那些对现在的你来说还非常生硬的文字概念——从抽象去理解抽象是意淫，从具体去理解抽象才是学习。
从“爬楼梯”问题说起
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
这道题目有两个关键的特征：
- 要求你给出达成某个目的的解法个数
- 不要求你给出每一种解法对应的具体路径
这样的问题，往往可以用动态规划进行求解
Step1：递归思想分析问题
基于动态规划的思想来做题，我们首先要想到的思维工具就是“倒着分析问题”。“倒着分析问题”分两步走：
- 定位到问题的终点
- 站在终点这个视角，思考后退的可能性
在这道题里，“问题的终点”指的就是走到第 n 阶楼梯这个目标对应的路径数，我们把它记为 f(n)。
那么站在第 n 阶楼梯这个视角， 有哪些后退的可能性呢？按照题目中的要求，一次只能后退 1 步或者 2 步。因此可以定位到从第 n 阶楼梯只能后退到第 n-1 或者第 n-2 阶。我们把抵达第 n-1 阶楼梯对应的路径数记为 f(n-1)，把抵达第 n-2 阶楼梯对应的路径数记为 f(n-2)，不难得出以下关系：
f(n) = f(n-1) + f(n-2)
f(1) = 1
f(2) = 2
function climbStairs(n) {
if (n === 1 || n === 2) return n;
return climbStairs(n - 1) + climbStairs(n - 2);
}
Step2：记忆化搜索来提效
重复计算带来了时间效率上的问题，要想解决这类问题，最直接的思路就是用空间换时间，也就是想办法记住之前已经求解过的结果。这里我们只需要定义一个数组：
const f = [];
每计算出一个 f(n) 的值，都把它塞进 f 数组里。下次要用到这个值的时候，直接取出来就行了：
/**
* @param {number} n
* @return {number}
*/
// 定义记忆数组 f
const f = [];
const climbStairs = function(n) {
if (n == 1) {
return 1;
}
if (n == 2) {
return 2;
}
// 若f[n]不存在，则进行计算
if (f[n] === undefined) f[n] = climbStairs(n - 1) + climbStairs(n - 2);
// 若f[n]已经求解过，直接返回
return f[n];
};
以上这种在递归的过程中，不断保存已经计算出的结果，从而避免重复计算的手法，叫做记忆化搜索。
Step3：记忆化搜索转化为动态规划
要想完成记忆化搜索与动态规划之间的转化，首先要清楚两者间的区别。
先说记忆化搜索，记忆化搜索可以理解为优化过后的递归。递归往往可以基于树形思维模型来做
我们基于树形思维模型来解题时，实际上是站在了一个比较大的未知数量级（也就是最终的那个 n），来不断进行拆分，最终拆回较小的已知数量级（f(1)、f(2)）。这个过程是一个明显的自顶向下的过程。
动态规划则恰恰相反，是一个自底向上的过程。它要求我们站在已知的角度，通过定位已知和未知之间的关系，一步一步向前推导，进而求解出未知的值。
在这道题中，已知 f(1) 和 f(2) 的值，要求解未知的 f(n)，我们唯一的抓手就是这个等价关系：
f(n) = f(n-1) + f(n-2)
以 f(1) 和 f(2) 为起点，不断求和，循环递增 n 的值，我们就能够求出 f(n)了：
const climbStairs = function(n) {
// 初始化状态数组
const f = [];
// 初始化已知值
f[1] = 1;
f[2] = 2;
// 动态更新每一层楼梯对应的结果
for (let i = 3; i <= n; i++) {
f[i] = f[i - 2] + f[i - 1];
}
// 返回目标值
return f[n];
};
从题解思路看动态规划
什么样的题应该用动态规划来做？我们要抓以下两个关键特征：
- 最优子结构
最优子结构，它指的是问题的最优解包含着子问题的最优解——不管前面的决策如何，此后的状态必须是基于当前状态（由上次决策产生）的最优决策。就这道题来说，f(n)和 f(n-1)、f(n-2)之间的关系印证了这一点（这玩意儿叫状态转移方程，大家记一下）。
- 重叠子问题
它指的是在递归的过程中，出现了反复计算的情况。
动态规划问题的分析技巧
分析路径
- 递归思想明确树形思维模型：找到问题终点，思考倒退的姿势，往往可以帮助你更快速地明确状态间的关系
- 结合记忆化搜索，明确状态转移方程
- 递归代码转化为迭代表达（这一步不一定是必要的，1、2 本身为思维路径，而并非代码实现。若你成长为熟手，2 中分析出来的状态转移方程可以直接往循环里塞，根本不需要转换）。
“最值”型问题典范：如何优雅地找硬币
给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
提示：最值问题是动态规划的常见对口题型，见到最值问题，应该想到动态规划
借助“倒推”的思想：解决爬楼梯问题时，我们首先思考的是站在第 n 阶楼梯上的后退姿势。这道题也一样，我们需要思考的是站在 amount 这个组合结果上的“后退姿势”—— 我们可以假装此时手里已经有了 36 美分，只是不清楚硬币的个数，把“如何凑到 36”的问题转化为“如何从 36 减到 0”的问题。
硬币的英文是 coin，因此我们这里用 c1、c2、c3......cn 分别来表示题目中给到我们的第 1-n 个硬币。现在我如果从 36 美分的总额中拿走一个硬币，那么有以下几种可能：
拿走 c1
拿走 c2
拿走 c3
......
拿走 cn
假如用 f(x）表示每一个总额数字对应的最少硬币数，那么我们可以得到以下的对应关系：
f(36) = Math.min(f(36-c1)+1,f(36-c2)+1,f(36-c3)+1......f(36-cn)+1)
这套对应关系，就是本题的状态转移方程。
找出了状态转移方程，我们接下来需要思考的是递归的边界条件：在什么情况下，我的“后退”（实际是做减法）可以停下来？这里需要考虑的是硬币总额为 0 的情况，这种情况对应的硬币个数毫无疑问也会是 0，因而不需要任何的回溯计算。由此我们就得到了一个已知的最基本的子问题的结果：
f[0] = 0
const coinChange = function(coins, 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);
}
}
}
// 若目标总额对应的解为无穷大，则意味着没有一个符合条件的硬币总数来更新它，本题无解，返回-1
if (f[amount] === Infinity) {
return -1;
}
// 若有解，直接返回解的内容
return f[amount];
};
0-1 背包模型
0-1 背包问题说的是这么回事儿：
有 n 件物品，物品体积用一个名为 w 的数组存起来，物品的价值用一个名为 value 的数组存起来；每件物品的体积用 w[i] 来表示，每件物品的价值用 value[i] 来表示。现在有一个容量为 c 的背包，问你如何选取物品放入背包，才能使得背包内的物品总价值最大？
思路分析
这道题最后问了“如何才能使背包内的物品总价值最大？”，我们前面讲过，遇到最值问题，一定要在可能的解题方案中给动态优化留下一席之地。事实上，背包系列问题，正是动态规划的标准对口问题。
“倒推”法明确状态间关系
现在，假设背包已满，容量已经达到了 c。站在 c 这个容量终点往后退，考虑从中取出一样物品，那么可能被取出的物品就有 i 种可能性。我们现在尝试表达“取出一件”这个动作对应的变化，我用 f(i, c) 来表示前 i 件物品恰好装入容量为 c 的背包中所能获得的最大价值。现在假设我试图取出的物品是 i，那么只有两种可能：
- 第 i 件物品在背包里
- 第 i 件物品不在背包里
如果说本来这个背包中就没有 i 这个东西，那么尝试取之前和尝试取之后，背包中的价值总量是不会发生变化的：
f(i, c) = f(i-1, c)
但如果背包中是有 i 的，那么取出这个动作就会带来价值量和体积量的减少：
f(i, c) - value[i] = f(i-1, c-w[i])
把这个减法关系稍微转化一下，变为加法关系：
f(i, c) = f(i-1, c-w[i]) + value[i]
可以看出，想要求出 f(i, c)，我们只要定位到正确的 f(i-1, c) 和 f(i-1, c-w[i]) + value[i] 的值，并且取出两者中较大的值就可以了
基于上面的分析，我们抽取出自变量和因变量：自变量是物品的索引（假设为 i）和当前背包内物品的总体积（假设为 v），因变量是总价值。我们仍然是用一个数组来记忆不同状态下的总价值，考虑到这道题中存在两个自变量，我们需要开辟的是一个二维数组。现在我利用二维数组来将上述的状态关系编码化：
dp[i][v] = Math.max(dp[i-1][v], dp[i-1][v-w[i]] + value[i])
现在我们来瞅瞅这个状态转移方程怎么往循环里塞才合适。仍然是从变量入手：变量是 i 和 v，但本质上来说 v 其实也是随着 i 的变化而变化的，因此我们可以在外层遍历 i、在内层遍历 v。
for (let i = 1; i <= n; i++) {
for (let v = w[i]; v <= c; v++) {
dp[i][v] = Math.max(dp[i - 1][v], dp[i - 1][v - w[i]] + value[i]);
}
}
对于第 i 行的计算来说，只有第 i-1 行的数据是有意义的，更早的数据它都不关心。也就是说我们其实根本不需要记录所有的数据，理论上只要保留当前行和上一行的数据就足够了。
插播小知识——滚动数组
这里要给大家介绍的是一种叫做“滚动数组”的编码思想——所谓“滚动数组”，顾名思义，就是让数组“滚动”起来：固定一块存储空间，滚动更新这块存储空间的内容，确保每个时刻空间内的数据都是当前真正会用到的最新数据，从而达到节约内存的效果，这种手段就叫做滚动数组。
用滚动数组来优化状态转移方程
我可以只定义一个一维数组，通过倒着遍历 v 的方法来实现数组的滚动更新：
for (let i = 1; i <= n; i++) {
for (let v = c; v >= w[i]; v--) {
dp[v] = Math.max(dp[v], dp[v - w[i]] + value[i]);
}
}
拿第 i-1 行和第 i 行来举例，首先我肯定是刷刷刷地用第 i-1 行的数据把一维数组给填满了
接下来我尝试用第 i 行的数据更新它。当数据更新走到 dp[i][v] 这里的时候，dp[i-1][v] 和 dp[i-1]v-w[i]] 都是存在的状态（分别对应一维数组中现在的 dp[v]和 dp[v-w[i]]的值，完全可以满足我们的计算需要：
// 入参是物品的个数和背包的容量上限，以及物品的重量和价值数组
function knapsack(n, c, w, value) {
// dp是动态规划的状态保存数组
const dp = new Array(c + 1).fill(0);
// res 用来记录所有组合方案中的最大值
let res = -Infinity;
for (let i = 0; i < n; i++) {
for (let v = c; v >= w[i]; v--) {
// 写出状态转移方程
dp[v] = Math.max(dp[v], dp[v - w[i]] + value[i]);
// 即时更新最大值
if (dp[v] > res) {
res = dp[v];
}
}
}
return res;
}
最长上升子序列模型
题目描述：给定一个无序的整数数组，找到其中最长上升子序列的长度。
思路分析
啥是“子序列”？它指的是在原有序列的基础上，删除 0 个或者多个数，其他数的顺序保持不变得到的结果。拿示例的这个序列来说：
这里我们关注到的就是“以序列中第 i 个元素为结尾的前 i 个元素的状态”。
我们用 f(i)来表示前 i 个元素中最长上升子序列的长度。若想基于 f(i) 求解出 f(i+1)，我们需要关注到的是第 i+1 个元素和前 i 个元素范围内的最长上升子序列的关系，它们之间的关系有两种可能：
- 若第 i+1 个元素比前 i 个元素中某一个元素要大，此时我们就可以在这个元素所在的上升子序列的末尾追加第 i+1 个元素（延长原有的子序列），得到一个新的上升子序列。
- 若第 i+1 个元素并不比前 i 个元素中所涵盖的最长上升子序列中的某一个元素大，则维持原状，子序列不延长。
/**
* @param {number[]} nums
* @return {number}
*/
// 入参是一个数字序列
const lengthOfLIS = function(nums) {
// 缓存序列的长度
const len = nums.length;
// 处理边界条件
if (!len) {
return 0;
}
// 初始化数组里面每一个索引位的状态值
const dp = new Array(len).fill(1);
// 初始化最大上升子序列的长度为1
let maxLen = 1;
// 从第2个元素开始，遍历整个数组
for (let i = 1; i < len; i++) {
// 每遍历一个新元素，都要“回头看”，看看能不能延长原有的上升子序列
for (let j = 0; j < i; j++) {
// 若遇到了一个比当前元素小的值，则意味着遇到了一个可以延长的上升子序列，故更新当前元素索引位对应的状态
if (nums[j] < nums[i]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
// 及时更新上升子序列长度的最大值
if (dp[i] > maxLen) {
maxLen = dp[i];
}
}
// 遍历完毕，最后到手的就是最大上升子序列的长度
return maxLen;
};
总结
最优解/最值
套路：选/不选