算法之动态规划

算法

动态规划算法
- 子结构递归式，使用递归方法求解依据
- 最优化子结构最优解递归式，自底向上求解依据
- 重叠子问题包含大量的重叠子问题的时候，使我们使用动态规划的依据
两种解法
- 自底向上动态规划
  - for循环从底层往上进行计算，然后递归的实现逻辑也比较方面的用for循环来实现
- 备忘录方法
  - 其实就是递归的基础上加了一张表，然后通过检查表中是否已经有数据了来判断是否已经求结果该问题，如果已经求结果了，那就直接返回结果就行了。
  - 递归方法递归写程序注意好边界返回值，然后开始将递归逻辑翻译一下就好了，注重逻辑，不要太关注递归运行执行，一棵树的回溯递归不是那么容易好想的
例子

最长公共子序列问题。给定两个子串，求取这两个子串的最长公共子序列。
- 最优子结构
  
  设序列X = {x1, x2, x3, ..., xm}, 序列 y = {y1, y2, y3, ... yn}的最长公共子序列 Z = {z1, z2, z3, ..., zk};则
  - 若 xm = yn,则 zk = xm = yn,且Zk-1 是Xm-1 和 Yn-1的最长公共子序列
  - 若 xm != yn，且xm != zk,则 Zk 是Xm-1 = {x1, x2, x3, ... xm-1} 和 Y 的最长公共子序列
  - 若 xm != yn 且yn != zk,则 Zk 是 X 和 Yn-1的最长公共子序列
- 递推公式转化
  
  这个地方有时候不能直接求取，可以先求选择变化的数组，将每次的选择路径记录下来，同时进行相关你的转化
  
  首先建立子问题最优值得递归关系，用c[i][j] 来记录序列Xi和Yj的最长公共子序列的长度。其中，Xi = {x1, x2, x3, ..., xi}, Yj = {y1, y2, y3, ...., yj}。当i = 0,或者j = 0的是空序列是最长公共子序列，故此时c[i][j] = 0。其他情况下的最有子结构建立的递推关系如下：
  
  c[i][j] = 0 where i = 0, or j = 0
  
  c[i][j] = c[i-1][j-1] where X[i] != Y[j], i > 0,j >0
  
  c[i][j] = max {c[i][j-1], c[i-1][j] } where i > 0, j > 0, X[i] != Y[j]
- 考虑求解最长公共子序列的其他的数据结构
  ：需要一个用来b[m+1][n+1]的数组用来记录Xi 与 Yj的最长公共子序列是属于上面三种情况的哪一种
- 以下分别使用自底向上的解法和备忘录的方法来求解，习惯递归结构的人，用备忘录方法来实现特别方便，一般来讲这种比较简单，对于自底向上的动态规划解法如果熟悉了也不是很难
```
import java.util.*;
```

public class Test {
public static void main(String args[]) {
Scanner scanner = new Scanner(System.in);
while (scanner.hasNext()) {
String aString = scanner.next();
String bString = scanner.next();
char[] aArray = aString.toCharArray();
char[] bArray = bString.toCharArray();
int [][]b = new int[aArray.length + 1][bArray.length + 1];
int [][]c = new int[aArray.length + 1][bArray.length + 1];
// lesLength(aArray, bArray, b);
recurseLesLength(aArray, bArray, aArray.length, bArray.length, b, c);
traceLes(aArray.length, bArray.length, aArray, b);
}
scanner.close();
}
public static void traceLes(int i,int j,char[]x,int [][]b) {
if (i == 0 || j == 0) return ;
if (b[i][j] == 1) {
traceLes(i-1, j - 1, x, b);
System.out.print(x[i-1]);
} else if (b[i][j] == 2) {
traceLes(i - 1, j, x, b);
} else {
traceLes(i, j - 1, x, b);
}
}
public static int recurseLesLength(char[] x, char[] y, int m, int n, int[][] b, int [][]c) {
if(c[m][n] > 0) return c[m][n];
if( m == 0 || n == 0) return 0;
if(x[m - 1] == y[n - 1]) {
b[m][n] = 1;
c[m][n] = 1 + recurseLesLength(x, y, m - 1, n -1, b, c);
return c[m][n];
}else {
int l1 = recurseLesLength(x, y, m - 1, n, b, c);
int l2 = recurseLesLength(x, y, m, n - 1, b, c);
if (l1 >= l2) {
b[m][n] = 2;
c[m][n] = l1;
return l1;
} else {
b[m][n] = 3;
c[m][n] = l2;
return l2;
}
}
}
public static int lesLength(char []x,char[] y,int[][] b) {
int m = x.length;
int n = y.length;
int [][]c = new int[m+1][n+1];
for(int i = 0; i <= m; i++) {
c[i][0] = 0;
}
for(int i = 0; i <= n; i++) {
c[0][i] = 0;
}
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (x[i - 1] == y[j - 1]) {
c[i][j] = c[i-1][j-1] + 1;
b[i][j] = 1;
} else if (c[i][j-1] <= c[i-1][j]){
c[i][j] = c[i-1][j];
b[i][j] = 2;
} else {
c[i][j] = c[i][j - 1];
b[i][j] = 3;
}
}
}
return c[m][n];
}
}
```