#算法学习录#动态规划

动态规划应用于子问题重叠的情况。对于公共子问题，分治算法会做很多不必要的工作，它会反复求解公共子问题。而动态规划算法对每个子问题只求解一次，将其解保存于一个表格，从而每次求解一个子问题时都重复计算，避免了不必要的计算工作。
动态规划方法通常用于求解最优化问题。此类问题有许多可行解，从中找出有最优值的解。这样的解称为问题的一个最优解，而不是最优解（可能会有多个解均达到最优值）。

通常按下面四个步骤来设计动态规划算法：
1. 刻画一个最优解的结构特征。
2. 递归定义最优解的值。
3. 计算最优解的值。
4. 利用3的计算结果构造最优解。

讨论实例：1.钢条切割 2.最长公共子序列

1. 钢条切割：
钢条切割长度及其对应出售价格关系
长度i 1 2 3 4 5 6 7 8 9 10
价格pi 1 5 8 9 10 17 17 20 24 30
给定一段长度为n的钢条，和一个价格表，求切割钢条方案使得收益rn最大。

例如：一段长度为4的钢条可以获得的收益为9（不分割），1+8=9（切为长度为1,3的两段），5+5=10（切为两段长度为2），1+1+1+1=4（切为四段长度为1）…etc.最优策略方案为切为两段（5+5）的，收益为10。

对于rn，有下列最优切割方案的结构：
rn = max(pn, r1+rn-1, r2+rn-2,…, rn-1+r1)
s首次切割后，剩余两段钢条可以作为两个独立的钢条切割问题实例，并从中选取组合收益最大者，构成原问题的最优解，这满足最优子结构。

//至顶向下递归实现（非动态规划方法）,p:价格数组；n:钢条长度
int CUT_ROD(const int p[], int n){
 if (n == 0)
  return 0;
 int q = -199999;   //设置无穷大
 for (int i = 1; i <= n; ++i)
  q = MAX(q, p[i%12] + CUT_ROD(p, n - i));
 return q;
}
结果：
 

如果输入的数据很大（例如30）则运算结果可能要几分钟甚至几个小时才能运行完。这正是由于它反复求解重叠子问题，使运行时间程指数增长（2n）。

接下来用动态规划方法来处理切割问题。
第一种带备忘自顶向下法：
该方法用递归额方式求解问题，用一数组记录每个切割方案的解，求解时先检查是否已保存过此解，是，则返回返回保存值，否则，按常规方式求解该子问题。

//带备忘自顶向下法（动态规划）
int Memoized_Cut_Rod(const int p[],int n){
 int *r = new int[n + 5];  //创建备忘录
 for (int i = 0; i <= n + 5; i++){
  r[i] = -1999999;
 }
 return Memoized_Cut_Rod_Aux(p,n,r);
}
//带备忘自顶向下法（动态规划）辅助过程
int Memoized_Cut_Rod_Aux(const int p[], int n, int r[]){
 int q;
 if (r[n] >= 0)   //检查备忘录
  return r[n];
 if (n == 0)
  q = 0;
 else{
  q = -199999;
  for (int i = 1; i <= n; i++) //递归求解
   q = MAX(q, p[i%12] + Memoized_Cut_Rod_Aux(p, n - i, r));
 }
 r[n] = q;  //备忘结果
 return q;
}
结果：

 
输入99999999后：

 
由于递归的开销比较大，当n较大时可能会发生栈溢出（直接宕机了。。。后果非常严重！！）。

自底向上版本：
也有备忘录。按由小到大的顺序求解，即从长度为1开始求解，直到n，使每个子问题只求解一次，且，不用递归的方式，使系统开销更小。

//自底向上法方（动态规划）
int Bottom_up_Cut_Rod(const int p[], int n){
 int q;
 int *r = new int[n + 1];
 r[0] = 0;
 for (int j = 1; j <= n; ++j){
  q = -1099999;
  for (int i = 1; i <= j; ++i){
   q = MAX(q, p[i%12] + r[j - i]);
  }
  r[j] = q;
 }
 return r[n];
}
结果：

 
当然，只是知道最优收益是不够的，还需要知道具体切割方案！~
重构解：用S[]记录最优解对应第一段钢条的切割长度。
重构解，返回最优方案
int Extended_Bottom_up_Cut_Rod(const int p[], int n, int s[]){
 int q;
 int *r = new int[n + 1];
 r[0] = 0;
 for (int j = 1; j <= n; ++j){
  q = -10999;
  for (int i = 1; i <= j; i++){
   if (q < p[i % 12] + r[j - i]){
    q = p[i % 12] + r[j - i];
    s[j] = i;
   }
  }
  r[j] = q;
 }
 return r[n];
}
cout << "最优切割方案(分段长度)：";
while (n > 0){
 cout << s[n] << " ";
 n = n - s[n];
 }
结果：

2. 最长公共子序列（longest-common-subsequence problem LCS）
对序列X= <x1,x2,x3,x4…>，Y= <y1,y2,y3,y4…>,如果Z既是X的子序列，也是Y的子序列，则称它为X，Y的公共子序列，如：X=<A,B,C,B,D,A,B>,Y=<B,D,C,A,B,A>,那么序列<B,C,A>是X，Y的公共子序列（长度为3），而序列<B,C,A,B>也是X，Y的公共子序列（长度为4）
1. 刻画一个最优解的结构特征。
有序列X= <x1,x2,x3,x4…xm>，Y= <y1,y2,y3,y4…yn>，序列Z=<z1,z2,z3,…,zk>为X、Y的任意LCS。
1如果xm = yn ，则zk = xm = yn 且Zk-1 是Xm-1和Yn-1的一个LCS。
  2如果xm != yn ，则zk != xm 为 Z 是Xm-1和Y的一个LCS。
  3如果xm != yn ，则zk!= yn  为Z 是X和Yn-1的一个LCS。
2. 递归定义最优解的值。
  0  //i==0 or j==0
b[i][j].length =  b[i-1][j-1].length+1 //xi==yj
      MAX（b[i][j-1].length, b[i-1][j].length）//xi!=yj
3. 计算LCS的长度。
void LCS_LENGTH(char x[], int m, char y[], int n, table **b){
 for (int i = 0; i <= m; i++)   //初始化表格
  for (int j = 0; j <= n; j++)
   b[i][j].length = 0;

 for (int i = 1; i <= m; i++){
  for (int j = 1; j <= n; j++){
   if (x[i] == y[j]){
    b[i][j].length = b[i - 1][j - 1].length + 1;
    b[i][j].direction = ‘↖’;
   }
   else if (b[i - 1][j].length >= b[i][j - 1].length){
    b[i][j].length = b[i - 1][j].length;
    b[i][j].direction = ‘↑’;
   }
   else{
    b[i][j].length = b[i][j - 1].length;
    b[i][j].direction = ‘←’;
   }
  }
 }
}
4. 利用3的计算结果构造最优解。
void PRINT_LCS(table **b, char x[], int m, int n){
 if (m == 0 || n == 0)
  return;
 if (b[m][n].direction == ‘↖’){
  PRINT_LCS(b, x, m - 1, n - 1);
  cout << x[m];
 }
 else if (b[m][n].direction == ‘↑’)
  PRINT_LCS(b, x, m - 1, n);
 else PRINT_LCS(b, x, m, n - 1);
}
其中：table整合了长度和方向信息。
typedef struct table{
 int length;
 char direction;
}table;

结果：

最后附上源代码：https://github.com/LRC-cheng/Algorithms_Practise.git