LCS的两种解法比较
动态规划问题一般具有两个要素：最优子结构与子问题重叠。
通常在求解LCS问题时，我们都会用到两种方法：
1. momo-ization（备忘录方法）
利用了该问题的重叠子问题特性，而重叠子问题可以使用递归直接解决
| 0 | A | B | C | B | D | A | B | |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| B | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
| D | 0 | 0 | 1 | 1 | 1 | 2 | 2 | 2 |
| C | 0 | 0 | 1 | 2 | 2 | 2 | 2 | 2 |
| A | 0 | 1 | 1 | 2 | 2 | 2 | 3 | 2 |
| B | 0 | 1 | 2 | 2 | 3 | 3 | 3 | 4 |
| A | 0 | 1 | 2 | 2 | 3 | 3 | 4 | 4 |
也就是上表中从最后一格向上回溯直到哨兵的过程，在求解每个子问题之前，我们先检测一下这个子问题之前有没有算过，若果有，那么不用计算直接返回结果，如果没有，那么就计算这个子问题，之后将结果保存起来，方便下次再遇到时使用。。
时间复杂度T(n) = O(mn);
空间复杂度S = O(mn); //二维数组
public class TTBlcs {
static int[][] c = new int[100][100];
static int NIF = 9999;
public static void main(String[] args) {
char[] x = {'A','B','C','B','D','A','B'};
char[] y = {'B','D','C','A','B','A'};
//TTBlcs t = new TTBlcs();
for(int i = 0;
i <= x.length;
i++){//周围有一圈哨兵均为0
for(int j = 0;
j <= y.length;
j++)
{
c[i][j] = NIF;
}
}
System.out.print(LCS(x,y,x.length,y.length));
//自上而下
}
public static int LCS(char[] x,char[] y,int i,int j){
if(c[i][j] < NIF)//记录如果算出来便直接返回（备忘）
return c[i][j];
if((i == 0)||(j == 0)){
c[i][j] = 0;
}
else if(x[i-1] == y[j-1])
c[i][j] = LCS(x,y,i-1,j-1) + 1;
else
c[i][j] = LCS(x,y,i-1,j) >= LCS(x,y,i,j-1)? LCS(x,y,i-1,j):LCS(x,y,i,j-1);
return c[i][j];
}}2. 动态规划DP：
所谓自下而上，就是从下标(1,1)处开始求解的过程，不过省去了递归的过程，自下而上的构建原问题的解，首先求解最基本的情况，再从最基本的情况一部一部的向上求解，比如我要求解[2…4]，那么我首先需要知道[2…2][3…4]和[2…3][4…4]的最优解，需要知道[3…4]，那么首先需要知道[3…3][4…4]的最优解，所以，倒不如我们将原问题需要的解先构建出来，再慢慢向上一层一层的构建，最后组成原问题的解！。
时间复杂度T(n) = O(mn);
【LCS的两种解法比较】空间复杂度S = O(mn); //二维数组
public class BTTlcs {
static int[][] c = new int[100][100];
public static void main(String[] args) {
char[] x = {'A','B','C','B','D','A','B'};
char[] y = {'B','D','C','A','B','A'};
for(int k = 0;
k <= x.length;
k++)
{
c[0][k] = 0;
}
for(int k = 0;
k <= y.length;
k++)
{
c[k][0] = 0;
}
LCS(x,y);
}
public static void LCS(char[] x,char[] y){
for(int i = 1;
i <= x.length;
i++)
{
for(int j = 1;
j <= y.length;
j++)
{
if(x[i-1] == y[j-1])
c[i][j] = c[i-1][j-1] + 1;
else
c[i][j] = c[i-1][j] >= c[i][j-1]?c[i-1][j]:c[i][j-1];
}
}
for(int i = 0;
i <= x.length;
i++)
{
for(int j = 0;
j自上而下的 优点是并不需要求解每一个子问题的解，而是只求解有需要的子问题的解， 缺点就是需要递归调用，函数调用浪费时间。自下而上的 优点是并不需要递归调用，每个子问题求解的速度较快， 缺点每个子问题都要计算，就算这个子问题的解对原问题的解并没有任何帮助！
??
推荐阅读
- 热闹中的孤独
- JAVA（抽象类与接口的区别&重载与重写&内存泄漏）
- 放屁有这三个特征的，请注意啦！这说明你的身体毒素太多
- 一个人的旅行，三亚
- 布丽吉特，人生绝对的赢家
- 慢慢的美丽
- 尽力
- 一个小故事，我的思考。
- 家乡的那条小河
- 《真与假的困惑》???|《真与假的困惑》??? ——致良知是一种伟大的力量