动态规划法

基本思想

利用问题的最优子结构构造动态函数，通过递推计算得到问题的解，再通过回溯得到问题解的具体形式

特征：
（1）最优子结构
（2）子问题重叠

基本步骤：
（1）寻找递推式（核心）
（2）设置初始解
（3）填表，求解问题
（4）回溯，得到问题解的具体形式

数塔问题

多段图最短路径问题

递推式为：

d(0,j) = min ( d(0,s) + Cs,j )

解题思路：

d(0,4) = min(d(0,1) + C1,4, d(0,2) + C2,4) = 8
d(0,5) = min(d(0,1) + C1,5, d(0,2) + C2,5, d(0,3) + C3,5) = 7
d(0,6) = min(d(0,2) + C2,6, d(0,3) + C3,6) = 10

d(0,7) = 13
d(0,8) = min(d(0,4) + C4,8, d(0,5) + C5,8,d(0,6) + C6,8) = 13

d(0,9) = min(d(0,7) + c7,9, d(0,8) + c8,9) = 16

故最短路径为：16

时间复杂度：
O(m+k)，其中，m为图的边数，k为图的段数

最长递增子序列

递推式：

时间复杂度：

O(n^2)

0/1背包问题

考虑5个物品，重量分别是{2, 2, 6, 5, 4}，价值分别为{6, 3, 5, 4, 6}，背包容量为10

初始值：
1、不往背包里放物品，即C(0, )，背包最大价值为0；
2、背包不能装任何东西，即C(, 0)，背包最大价值也是0。

V[5,10]>V[4,10] => 第五个物品装进背包，背包容量减到6

V[4,6]=V[3,6]=V[2,6] => 不装进背包，向上回溯

V[2,6]>V[1,6] => 第2个物品装入背包，背包容量减到4

V[1,4]>V[0,4] => 第1个物品装入背包，背包容量减到2

时间复杂度：

O(n×C)，n为物品数，C为背包大小