动态规划
动态规划（Dynamic programming）将问题分拆成一个个子问题，通过解决子问题来推原问题的解。
重要的是推出状态转移方程，例 $f(n) = f(n-1) + f(n-2)$
这里明显 $f(n)$ 用到了不止一次，所以要记录下每次 $f(n)$ 和 $f(n-1)$ 的结果。
动态规划从子问题开始，所以直接从 $f(1)$ 开始算起并记录。
背包问题
背包问题(Knapsack problem)是一种组合优化的NP完全问题。问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。
上BGM：
0−1 背包问题
每件物品只能用一次。
思路：利用 $f(x,y)$ 表示选择前 $x$ 个物品，装到容量为 $y$ 的背包中的物品的价值的最大值。
- 如果第 $x$ 个物品的重量 $w_x$ 大于背包的容量 $y$，则 $x$ 不能被放入背包中，$f(x,y) = f(x-1,y)$
- 如果背包足够大，能放下第 $x$ 个物品，则 $f(x,y) = f(x-1,y) + x$
- 如果背包要放入 $x$ 需要取出之前的物品，则需要考虑置换之后价值有无增加：比较 $f(x-1,y)$ 与 $f(x-1,y-w_x) + x$ ，取较大值。
思路二：循环时从大到小
待续……