0. 心得
- 尝试用动态规划时，思考 n 代表什么，f(n) 代表什么意思
- 尝试写出 f(n) 和 f(n +- 1) 的转移方程
1. 如何判断是动态规划
- 求最值，需要穷举，循环迭代
- 一定具有最优子结构（子问题间必须相互独立）
2. 动态规划步骤
- 有什么状态
- 只要是个变量，就可能是状态，例如 dp 数组索引
- 每个【状态】，可以做什么【选择】使得【状态】改变
- 如何定义 DP table/函数来表现【状态】和【选择】
- Base Case 是什么
即【状态】【选择】【DP数组】的定义
当以上都确定好后，进一步实现和优化
- 写出暴力解法（只有当状态、选择、DP table都定义好后才能写出）
- 利用DP表解决重叠子问题
- 状态压缩，优化DP table
3. 动态规划框架
js
// 初始化base case
const dp[0][0][...] = base case
// 进行状态转移
for 状态1 in 状态1所有值
for 状态2 in 状态2所有值
for ...
dp[状态1][状态2][...] = 求最值(选择1, 选择2, ...)
熟记此概念：dp[状态1][状态2][...] = 求最值(选择1, 选择2, ...)
构建思路
js
// 最值 => 穷举 循环迭代
// 具有最优子结构 => 动态规划 硬币数无限，子问题间相互独立
// 定义
// 1. 状态：什么是可变的，凑成的目标金额为状态
// 2. 选择：什么可以改变状态，选择硬币，需要凑成的目标金额便减小。选硬币的额度为选择。
// 3. DP table： 一般拿状态和所求做映射，此处求金额n的最少硬币数，那DP table代表金额n所需要的最少硬币数
// 4. base case: 初始化最简单情况 dp[0] = 0
4. 细化问题点
4.1 状态转移方程
- 确定状态：确定好原问题和子问题中的变量。
找出哪个是可变的，向着basecase去接近。
例如凑硬币题目：硬币数量无限，硬币的面额和目标金额是给定的，只有目标金额会不断向base case靠近
目标金额就是唯一的【状态】 - 确定选择：导致状态产生变化的行为
目标金额为什么会变化，因为在选择硬币，选择硬币后就减少目标金额。所有硬币的面额就是【选择】 - 确定 DP table
- 确定 base case
注意：状态方程不要惯性思维理解为 f(n) 与 f(n-1) 的关系，而是 f(n) 与 f(n +- i) 的关系
4.2 消除重叠子问题
动态规划问题的第一个性质，需要用备忘录或 DP table 去解决。
DP table 一般自底向上
4.3 最优子结构
动态规划问题的第二个性质，子问题间必须相互独立。
4.4 无后效性
4.5 解题思路
- 求最大相差值，可以转移问题，求两最值，动态规划求最高值和最低值，然后两者相减得出。
- 遍历方向：
- 遍历的过程中，所需的状态必须是已经计算出来的。
- 遍历结束后，存储结果的那个位置必须已经被计算出来。