动态规划（Dynamic Programming，简称 DP），适用于具有重叠子问题和最优子结构的问题
难点：状态定义 和 状态转移方程
方法步骤：
- 确定 dp 数组及下标的含义
- 确定递推公式
- dp 数组初始化
- 确定遍历顺序
- 举例推导dp数组
重叠子问题
leetcode：
- 509. 斐波那契数 - 力扣（LeetCode）
- 70. 爬楼梯 - 力扣（LeetCode）
- 746. 使用最小花费爬楼梯 - 力扣（LeetCode）
- 62. 不同路径 - 力扣（LeetCode）
- 63. 不同路径 II - 力扣（LeetCode）
- 343. 整数拆分 - 力扣（LeetCode）
打家劫舍问题
leetcode：
买卖股票问题
leetcode：
不限交易次数：
- 122. 买卖股票的最佳时机 II - 力扣（LeetCode） （不限交易次数）
- 309. 买卖股票的最佳时机含冷冻期 - 力扣（LeetCode） （不限交易次数）
- 714. 买卖股票的最佳时机含手续费 - 力扣（LeetCode） （不限交易次数）
交易至多（恰好） k 次：
- 121. 买卖股票的最佳时机 - 力扣（LeetCode） （交易恰好一次）
- 123. 买卖股票的最佳时机 III - 力扣（LeetCode） （交易最多 2 次）
- 188. 买卖股票的最佳时机 IV - 力扣（LeetCode） （交易最多 k 次）
线性 dp
leetcode：
二维 dp
leetcode：
编辑距离：
- 392. 判断子序列 - 力扣（LeetCode） （删除）
- 583. 两个字符串的删除操作 - 力扣（LeetCode） （删除）
- 72. 编辑距离 - 力扣（LeetCode） （删除、新增、变更）
区间 dp
leetcode：
- 647. 回文子串 - 力扣（LeetCode） （连续，非空）
- 5. 最长回文子串 - 力扣（LeetCode） （连续，非空）
- 516. 最长回文子序列 - 力扣（LeetCode） （不连续，可空）
连续的问题 dp 采用 true/false，也可以采用中心扩展法
不连续的问题 dp 采用 长度
背包问题
分为 0-1背包 和 完全背包，区别是 0-1 背包中的物品只有一个，完全背包的物品有无数个
0-1 背包
第一步，确定 dp 数组及下标的含义：
dp[i][j]：表示从下标为 [0 ~ i] 的物品里任意取，放进容量为 j 的背包，价值总和最大是多少
第二步，确定递推公式：
求 dp[i][j] 需要分为 2 种情况：
- 不放物品 i：其实就是相当于在
[0 ~ i-1]里选物品，所以等于dp[i-1][j] - 放物品 i：那么就要留出空间放 i，背包容量就变成了
j - weight[i]，相当于求在[0 ~ i-1]里选物品满足容量为j - weight[i]的最大价值，并且再加上物品 i 的价值，所以等于dp[i-1][j-weight[i]] + value[i]最终取它们中的最大值：dp[i][j] = Math.max( dp[i-1][j], dp[i-1][j-weight[i]] + value[i] )
第三步，dp 数组初始化：
根据递推公式，i 需要由 i-1 推出，所以先初始化 i 为 0 的情况
其他地方都初始化为 0 即可，因为都会在推导过程中被重新覆盖
第四步，确定遍历顺序：
先遍历物品还是先遍历背包重量？
因为 dp[i][j] 是根据左上角的 dp 数据推导而来，所以两种方式遍历都可以
1.先遍历物品，再遍历背包重量：
// weight 数组的大小 就是物品个数
for (let i = 1; i < weight.length; i++) { // 遍历物品
for (let j = 0; j <= bagweight; j++) { // 遍历背包容量
if (j < weight[i]) dp[i][j] = dp[i - 1][j] // 背包放不下物品 i，所以只考虑不放物品 i 的情况
else dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])
}
}2.先遍历背包容量，再遍历物品：
for (let j = 0; j <= bagweight; j++) { // 遍历背包容量
for (let i = 1; i < weight.length; i++) { // 遍历物品
if (j < weight[i]) dp[i][j] = dp[i - 1][j] // 背包放不下物品 i，所以只考虑不放物品 i 的情况
else dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])
}
}优化
将二维 dp 数组改为一维滚动数组：
因为每次赋值都是根据 正上方 和 左上方 数据得来，所以如果把 dp[i - 1] 那一层拷贝到 dp[i] 上，表达式完全可以是：dp[i][j] = Math.max(dp[i][j], dp[i][j-weight[i]] + value[i])
所以可以直接把 i 去掉，递推公式变为：dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i])
初始化：
背包容量为 0 时，装的价值最大为 0，所以 dp[0] = 0，其他情况下，根据递推公式得知需要取最大值，所以默认一个最小的数 0 即可。所以全部初始化为 0
遍历顺序：
正序 or 倒序？
如果正序遍历，那么后面求的值，用的是前面被更新覆盖后的值，无法读到原始值，且表示物品可以被添加多次，所以只能倒序遍历。
先物品 or 先背包？
只能先物品再背包，因为先背包的话，相当于二维里竖着更新，此时由于倒序遍历，前面的值还没有更新，所以读不到左上角的值。
而先物品的话是横着更新，前面的值已经计算过，可以读取到。
所以最终只有一种遍历方式：
for (let i = 0; i < weight.length; i++) { // 遍历物品
for (let j = bagweight; j >= weight[i]; j--) { // 遍历背包容量，因为 j < weight[i] 时不用更新，所以跳过
dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i])
}
}leetcode：
- 416. 分割等和子集 - 力扣（LeetCode） （0-1背包-true/false问题）
- 1049. 最后一块石头的重量 II - 力扣（LeetCode） （0-1背包-最大最小值问题）
- 494. 目标和 - 力扣（LeetCode） （0-1背包-组合数问题）
- 474. 一和零 - 力扣（LeetCode） （0-1背包-多维背包）
完全背包
和 0-1 背包的区别：同一个物品可以被放入无数次 所以，递推公式：
- 不放物品 i：其实就是相当于在
[0 ~ i-1]里选物品，所以等于dp[i-1][j] - 放物品 i：那么就要留出空间放 i，背包容量就变成了
j - weight[i]，区别在放了物品 i，还是可以再放物品 i。所以相当于求在[0 ~ i]里选物品满足容量为j - weight[i]的最大价值，并且再加上物品 i 的价值，所以等于dp[i][j-weight[i]] + value[i]
优化
正序 or 倒序？
物品可以被添加多次，所以采用正序遍历
先物品 or 先背包？
求组合数（不强调元素之间的顺序）：外层物品，内层背包
求排列数（强调元素之间的顺序）：外层背包，内层物品
无要求：顺序都可以
先物品后背包遍历方式：
for (let i = 0; i < weight.length; i++) { // 遍历物品
for (let j = weight[i]; j <= bagweight; j++) { // 遍历背包容量，因为 j < weight[i] 时不用更新，所以直接从 weight[i] 开始遍历
dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i])
}
}先背包后物品遍历方式：
for (let i = 0; i <= bagweight; i++) { // 遍历背包
for (let j = 0; j < weight.length; j++) { // 遍历物品
if (i >= weight[j]) {
dp[i] = Math.max(dp[i], dp[i - weight[j]] + value[j])
}
}
}leetcode：
- 322. 零钱兑换 - 力扣（LeetCode） （完全背包-最大最小问题）
- 518. 零钱兑换 II - 力扣（LeetCode） （完全背包-组合数问题）
- 377. 组合总和 Ⅳ - 力扣（LeetCode） （完全背包-排列数问题）
- 139. 单词拆分 - 力扣（LeetCode） （完全背包-排列数+true/false问题）