和递归相反，递归是由大的规模，逐渐划归为小问题，而动态规划同样有这样一个递推式子，但是从小的规模开始，一路生成数据规模越来越大的表，通过表格（空间复杂度）的查表操作，降低了递归空间的重复计算造成的时间浪费。

初探

  1. 递推

当一维状态不能很好的满足递归关系，可以用二维状态进行递归：
image.png

  1. 记忆化搜索

查表求值
image.png
如果使用递归，写一个func，会得到一个指数级时间的方法。使用查表，时间复杂度为立方级。

  1. 状态和状态转移

状态为解决一个问题的中间结果。当使用动规解决问题，设计合理的状态是解决问题的关键，他会让状态递归方程大大简化(考虑之前的一维变二维)。

  1. 最优子结构和最优化原理

举例： 最长单调递增子序列

  1. 决策和无后效性

一个状态演变到另一个状态，往往是通过“决策”来进行的。有了“决策”，就会有状态转移。而无后效性，就是一旦某个状态确定后，它之前的状态无法对它之后的状态产生“效应”（影响），马尔科夫性质。
泊松特性，一旦我等到了车，那么之前无论我等多久，都对下一次来车没有任何影响。

经典模型

1. 线性模型

线性模型的是动态规划中最常用的模型，上文讲到的最长单调子序列就是经典的线性模型，这里的线性指的是状态的排布是呈线性的。

【例题6】在一个夜黑风高的晚上，有n（n <= 50）个小朋友在桥的这边，现在他们需要过桥，但是由于桥很窄，每次只允许不大于两人通过，他们只有一个手电筒，所以每次过桥的两个人需要把手电筒带回来，i号小朋友过桥的时间为T[i]，两个人过桥的总时间为二者中时间长者。问所有小朋友过桥的总时间最短是多少。

解答：
每次过桥的时候最多两个人，如果桥这边还有人，那么还得回来一个人（送手电筒），也就是说N个人过桥的次数为2N-3（倒推，当桥这边只剩两个人时只需要一次，三个人的情况为来回一次后加上两个人的情况…）。有一个人需要来回跑，将手电筒送回来（也许不是同一个人，realy？！）这个回来的时间是没办法省去的，并且回来的次数也是确定的，为N-2，如果是我，我会选择让跑的最快的人来干这件事情，但是我错了…如果总是跑得最快的人跑回来的话，那么他在每次别人过桥的时候一定得跟过去，于是就变成就是很简单的问题了，花费的总时间：
T = minPTime (N-2) + (totalSum-minPTime)
来看一组数据 四个人过桥花费的时间分别为 1 2 5 10，按照上面的公式答案是19，但是实际答案应该是17。
具体步骤是这样的：
第一步：1和2过去，花费时间2，然后1回来（花费时间1）；
第二歩：3和4过去，花费时间10，然后2回来（花费时间2）；
第三部：1和2过去，花费时间2，总耗时17。
所以之前的贪心想法是不对的。
我们先将所有人按花费时间递增进行排序，假设前i个人过河花费的最少时间为opt[i]，那么考虑前i-1个人过河的情况，即河这边还有1个人，河那边有i-1个人，并且这时候手电筒肯定在对岸，所以
opt[i] = opt[i-1] + a[1] + a[i] (让花费时间最少的人把手电筒送过来，然后和第i个人一起过河)
如果河这边还有两个人，一个是第i号，另外一个无所谓，河那边有i-2个人，并且手电筒肯定在对岸，所以
opt[i] = opt[i-2] + a[1] + a[i] + 2a[2] (让花费时间最少的人把电筒送过来，然后第i个人和另外一个人一起过河，由于花费时间最少的人在这边，所以下一次送手电筒过来的一定是花费次少的，送过来后花费最少的和花费次少的一起过河，解决问题)
所以 opt[i] = min{opt[i-1] + a[1] + a[i] , opt[i-2] + a[1] + a[i] + 2a[2] }

2. 区间模型

区间模型的状态表示一般为d[i][j]，表示区间[i, j]上的最优解，然后通过状态转移计算出[i+1, j]或者[i, j+1]上的最优解，逐步扩大区间的范围，最终求得[1, len]的最优解。

【例题7】给定一个长度为n（n <= 1000）的字符串A，求插入最少多少个字符使得它变成一个回文串。**

典型的区间模型，回文串拥有很明显的子结构特征，即当字符串X是一个回文串时，在X两边各添加一个字符’a’后，aXa仍然是一个回文串，我们用d[i][j]来表示A[i…j]这个子串变成回文串所需要添加的最少的字符数，那么对于A[i] == A[j]的情况，很明显有 d[i][j] = d[i+1][j-1] （这里需要明确一点，当i+1 > j-1时也是有意义的，它代表的是空串，空串也是一个回文串，所以这种情况下d[i+1][j-1] = 0）；当A[i] != A[j]时，我们将它变成更小的子问题求解，我们有两种决策：
1、在A[j]后面添加一个字符A[i]；
2、在A[i]前面添加一个字符A[j]；
根据两种决策列出状态转移方程为：
d[i][j] = min{ d[i+1][j], d[i][j-1] } + 1; (每次状态转移，区间长度增加1)
空间复杂度O(n，时间复杂度O(n)， 下文会提到将空间复杂度降为O(n)的优化算法。

3. 背包

1. 01背包

题目：有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使价值总和最大。
状态转移方程：

  1. f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}

基础解答：

  1. for i=1..N
  2.     for v=V..0
  3.         f[v]=max{f[v],f[v-c[i]]+w[i]};

一维：

  1. // 过程ZeroOnePack，表示处理一件01背包中的物品，两个参数cost、weight分别表明这件物品的费用和价值
  2. procedure ZeroOnePack(cost,weight)
  3.     // 费用为cost的物品不会影响状态f[0..cost-1]
  4.     // 倒序遍历 保证在新的一轮(i+1)时 f[v]中v大的值不会v小的值的影响，如f[10]=max{f[10-5]+10,f[10]},
  5.     // 此时f[5]还没有受到污染，即f[i][5]
  6.     for v=V..cost
  7.         f[v]=max{f[v],f[v-cost]+weight}
  9. for i=1..N
  10.     ZeroOnePack(c[i],w[i]);

恰好装满：在初始化时除了f[0]为0其它f[1..V]均设为-∞，如果不是刚好装满会得到f[4]=f[3]+f[1]=-∞

2. 完全背包

题目：有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
状态转移方程：

  1. f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0<=k*c[i]<=v}

基础解答：

  1. for i=1..N
  2.     for v=0..V
  3.         f[v]=max{f[v],f[v-cost]+weight}

一维：

  1. procedure CompletePack(cost,weight)
  2.     // 正序 和01相反，需要前面的收到污染 f[10]={f[10-4]+40,f[10]},f[6]={f[6-4]+40,f[10]}此时引入
  3.     // 了重量为4的物品，可以选择用2次
  4.     for v=cost..V
  5.         f[v]=max{f[v],f[v-c[i]]+w[i]}
  7. for i=1..N
  8.     procedure(c[i],w[i]);

3. 多重背包

题目：有N种物品和一个容量为V的背包。第i种物品最多有n[i]件可用，每件费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
状态转移方程：

  1. f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0<=k<=n[i]}

一维：

  1. procedure MultiplePack(cost,weight,amount)
  2.     if cost*amount>=V
  3.         CompletePack(cost,weight)
  4.         return
  5.     integer k=1
  6.     // n[i]=13 k=1,2,4, amount=6
  7.     while k<amount
  8.         ZeroOnePack(k*cost,k*weight)
  9.         amount=amount-k
  10.         k=k*2
  11.     ZeroOnePack(amount*cost,amount*weight)
  13. for i=1..N
  14.     procedure(c[i],w[i],n[i]);