动态规划

适用场景

如果一个问题具有以下两个特征：

1. 最优子结构(optimal substructure)。父问题的最优解包含子问题的最优解，只有先求出所有子问题的最优解，才能求出父问题的最优解
2. 重叠字问题(overlapping subproblems)。一个子问题被多个父问题使用到

那么这个问题就可以用动态规划来解决。

例如斐波那契数这题，$f(n) = f(n-1) + f(n-2)$，

• 父问题的解包含子问题的解，对于 $f(n)$, 只有先求出 $f(n-1)$ 和 $f(n-2)$，才能求出 $f(n)$
• $f(n-2)$ 被 $f(n)$ 和 $f(n-1)$ 两个父问题使用到

因此这题可以用动态规划来解决。

状态转移方程

要攻克一个动态规划问题，最重要的就是要找出它的状态转移方程，类似于下面这样：

$f(x, y, z) = f(x1, y1, z1) + f(x2, y2, z2) + ...$

思考的步骤分为5步：

1. 确定原子问题(base case)，即最小的不可分割的原子问题。例如斐波那契数列，有两个原子问题，$f(0) = 0, f(1) = 1$
2. 确定变量，即函数有多少个输入参数，也就是父问题和子问题中会变化的变量。例如斐波那契数列，父问题$f(5)$和子问题$f(4)$ 的区别就是$n$，因此状态就是$n$。斐波那契数列这个问题比较简单，只有一个变量，有的动规问题会有多个变量。
3. 确定函数的返回值，一般就是题目所求的目标值。例如斐波那契数列，$f(n)$返回的是第n个斐波那契数。有的题目比较复杂，函数不是直接求解目标值，而是求解某种中间值。
4. 确定可选动作，也就是如何驱动父问题转移成子问题。例如斐波那契数列，$f(n) = f(n-1) + f(n-2)$，可选的动作有两种，减1和减2。
5. **确定递推方程，即父问题与子问题之间的等式关系。