理论知识

动态规划通常用来求解最优化问题。

最优化问题：这类问题的解可能有多个，每一个解对应一个值，我们希望寻找具有最优值的一个解。

适用于动态规划求解对最优子问题一般有两个要素：最优子结构和重叠子问题。

最优子结构是指：一个问题的最优解包含子问题的最优解；重叠子问题是指：问题的递归算法会反复求解相同的子问题

这里有一个要点，如何证明一个问题具有最优子结构性质？

我们采用复制—粘贴法：一般用反证法证明：假定子问题的解不是其自身的最优解，而存在“更优的解” ，那么我们可以从原问题的解中“剪切”掉这些“最优解”的部分，而将“更优的解”粘贴进去，从而得到原问题的一个“更优”解，这与最初的解是原问题最优解的前提假设相矛盾。因此，不可能存在“更优的解”。反之，原问题的子问题的解应是其自身的最优解——最优子结构性成立。

理解上面的知识之后，一般动态规划求解问题的步骤如下：

第一步：证明问题满足最优性原理

第二步：获得问题状态的递推关系式（即状态转移方程）

第三步：递归求解最优解的值

第四步：重构最优解

其中，状态转移方程的解释如下

状态转移方程： 第i+1阶段的状态变量x(i+1) 的值随x(i)和第i阶段的决策u(i)的值变化而变化，可以把这一关系看成(x(i)，u(i))与x(i+1)的函数对应关系，用x(i+1)=Ti(x(i),u(i))表示。

我们也可以用子问题图来模拟递归求解过程

子问题图： 用于描述子问题与子问题之间的依赖关系。

值得注意，动态规划具有无后效性

无后效性： 对任意的阶段i，阶段i以后的行为仅依赖于i阶段的

状态，而与i阶段之前过程是如何达到这种状态的方式无关，这种性

质称为无后效性。

最后我们理解一下动态规划为什么能够给计算性能带来改变？

若问题的决策序列由n次决策构成，而每次决策有p种选择，若采用枚举法，则可能的决策序列将有p的n次方个。而利用动态规划策略的求解过程中仅保存了所有子问题的最优解，而舍去了所有不能导致问题最优解的次优决策序列，所以可能有多项式的计算复杂度。

一、钢条切割问题

实际该问题也是完全背包问题

第一步：我们假设dpi表示长度为i的钢条的最大收益，可以用反证法证明其划分的子问题dpj和dpi-j均具有最优子结构性（这个方法是两半都可能再次切割），这个问题还可以简化，如果划分的两半，一段可以继续切割记dpj，固定另一端值为ri-j，问题可以更简化

第二步：求递推方程，由上可以知道dpi可以划分为dpj和ri-j,则dpi就等于max（dpj+ri-j）其中，j从1到i

第三步：递归或者迭代求解最优解

两种方法实质就是递归求解和迭代求解的过程，一般推荐用第二种方法，由较小的子问题求解较大的子问题，这个时候上文所述的子问题图就可以发挥作用，通过它你可以清晰的了解你最先要求解的较小子问题是什么！

第四步：重构解

如果需要我们给出怎样切割的序列，这怎么办，利用上文记录的数组，如果dp[n]-r[i]=dp[n-i],说明肯定划分了i长的一段，这样就可以得出一个解

下文附自己实现的代码：

#include<iostream>
#include<algorithm> 
using namespace std;
const int maxl=1000;
int dp[maxl],p[maxl];
//dp[i]和p[i]分别表示长度为i的钢条的最大收益和价格 
int main() {
  int n;
  scanf("%d",&n);
  for(int i=1;i<=n;i++)
  scanf("%d",&p[i]);
  fill(dp,dp+n+1,0); //初始化
  for(int i=1;i<=n;i++) //迭代求解最优解过程 
  for(int j=1;j<=i;j++)
  dp[i]=max(p[j]+dp[i-j],dp[i]);
  printf("%d\n",dp[n]);
  while(dp[n]) { //求解最优解序列 
  for(int i=1;i<=n;i++) 
  if(dp[n]-p[i]==dp[n-i]){
    printf("%d ",i);
    n=n-i;
  } 
  }  
  return 0; 
}

二、 01背包问题

问题： 有n 个物品，它们有各自的重量和价值，现有给定容量的背包，如何让背包里装入的物品具有最大的价值总和？

分析：这个问题和上诉问题的区别在于每一个物品只能选一次或不选

最开始以dp[i][v]来表示前i件物品容量为v时的最大价格

第一步：分析最优性结构：对于dp[i][v],如果第i件不选，则dp[i-1][v]一定是最优，如果选了，dp[i-1][v-w[i]]一定是最优，否则反证之

第二步:如上分析，dp[i][v]=max(dp[i-1][v],dp[i-1][v-w[i]]+p[i]

第三步：迭代求解

第四步：重构解：

这里01背包问题还可以空间优化，但是对第四步重构解的求解有些不利，两种方法各有千秋

三、矩阵链乘法问题

首先理解题意，下面这段话方便理解

而采用不同的括号得到标量乘法次数不一样

我们记dp[i][j]表示第i个矩阵到第j个矩阵的最小标量

第一步：证明最优子结构性质，不妨设dp[i][j]的最大值在k处分开括号，那dp[i][k]和dp[k+1][j]也一定是最优方案不然反证之

第二步：如上，dp[i][j]显然和dp[i][k]和dp[k+1][j]，前后两个形成的矩阵分布为piXpk，pkXpj，二者连起来又笑话pipjpk，所以状态转移方程可以列为min（dp[i][k]+dp[k+1][j]+pipjpk），k从i+1到j-1.

第三步：递归或迭代求解，迭代求解从小到大先求ij之间的间隔也可以越来越大

第四步：解重构，这个已经是二维，重构解最好在记录dp[i][j]时就用一个s[i][j]记录i到j矩阵最后一个分割的 位置k。

四、LCS问题

如上发问，我们记dp[i][j]为两个序列前i个和前j个的最长公共子序列

第一步：证明最优子结构，也顺路思考dp[i][j-1],dp[i-1][j],dp[i-1][j-1]之间的关系

第二步：求解递归方程，这里主要看待两个序列第i个字和第j个 的关系，如果相等，长度肯定是在dp[i-1][j-1]的基础是+1，如果不相等，则是max（dp[i][j-1],dp[i-1][j]）

第三步：求解最优值

第四步：求解序列

从上面可以知道可以在构成dp数组是同时构造一个s数组，直接用三种不同的值代表上面三种情况。

五、最优二叉搜索树

上面就是问题描述：

这个问题的关键就是在找树根，先给一串给好的序列，假设取第k位为树根，则其划分为左右两部分。

第一步：证明最优结构性，即证明左右子树也是最优二叉搜索树，易证

第二步：dp[i][j]表示最优从i到j二叉搜索树的期望代价，那么上面的dp[1][k-1],dp[k+1][n]j加上树根k后代价是多少？多了一层所以加了树根代价是两边期望和和两者之间所有代价和，k从1到n，我们找这值最小的一个。

第三步：迭代求解

第四步：解重构

此外的Bellman-ford 算法，dag最长路（关键路径）算法也应用了动态规划。