最长公共子序列是一个典型的动态规划的问题，遇到这个问题，想到使用动态规划去解，对于我来说，更多的是因为这是算法课上面一道典型例题，已经解法的框架已经被“背”下来了。
but，一道题，到底适不适合用动态规划？如果能用，要怎么使用？很多时候我并不是很清楚。
最近，把自己这段时间对动态规划新的理解和认识mark在这里。下面是正题。
动态规划的本质是去除递归的冗余计算，来大幅提高自己的性能，降低复杂度。
举一个简单的例子，对于斐波那契数列，使用递归的解法：
int fab(n):
if(n==0){
return 0;
}
if(n==1){
return 1;
}
else
fab(n-1)+fab(n-2);
递归的问题在于，把一个大问题分解为子问题，but在计算子问题的时候，重复计算了大量的至问题。
比如在计算fab(10)的时候，需要计算fab(9)和fab(8)。于是，递归分别独立的去算fab(8)和fab(9)。但是fab(8)是fab(9)的子问题，在计算fab(9)的时候，就已经计算出来了fab(8)，但是这个结果却没有被保存，在计算fab(8)的时候，又要重新计算一次。
一个简单的想法，就是把计算的子问题的结果缓存一下，比如：
int fab(int n,vector<int> &dp){
//使用dp来缓存子问题的答案
//对于一个递归的问题，先查看缓存,如果缓存里面有的话
if(dp[n]!=-1){ //等于-1表示没有缓存
return dp[n];
}
//如果缓存里面没有的话
if(n==0){
return 0;
}
if(n==1){
return 1;
}
//计算当前问题的结果，并保存在缓存里面
int res=fab(n-1,dp)+fab(n-2,dp);
dp[n]=res;
return res;
}
const int n=10;
vector<int> vi(n+1,-1);
cout<<fab(n,vi);
小结
举了一个斐波那契数列的例子，对于一个问题，我们可以从先写一个“暴力的算法”，比如使用递归来求解fab。然后，下面从暴力的算法里面找冗余的计算。找到冗余之后，使用数据结构缓存冗余的计算结果，这样就避免的冗余计算。
递归是自顶向下的，动归是自底向上的，然后，把缓存冗余的计算结果的计算过程，变成自底向上的过程，就变成符合动归格式的代码了。
举个例子，
最长公共子序列 lintcode 77题（ http://www.lintcode.com/zh-cn/problem/longest-common-subsequence/ ）
暴力递归
char * a="abcbdab";
const int len_a=7;
char * b="bdcaba";
const int len_b=6;
int mymax(int a,int b,int c){
int max_item1=max(a,b);
int max_item2=max(max_item1,c);
return max_item2;
}
//暴力递归
int search(int ida,int idb){
if(ida>len_a || idb>len_b){
return 0;
}
if(ida==len_a && idb==len_b){
return 0;
}
int ret1=-1000000; //表示一个很小的数
if(a[ida]==b[idb]){
ret1=search(ida+1,idb+1)+1;
}
return mymax(ret1,search(ida+1,idb),search(ida,idb+1));
}
加入缓存
int dp[len_a][len_b];
//加入了缓存
int search2(int ida,int idb){
if(ida>len_a || idb>len_b){
return 0;
}
if(ida==len_a && idb==len_b){
return 0;
}
//如果命中缓存
if(dp[ida][idb]!=-1){
return dp[ida][idb];
}
else{
//如果没有命中缓存
int ret1=-1000000;
if(a[ida]==b[idb]){
ret1=search2(ida+1,idb+1)+1;
}
int ret2=search2(ida+1,idb);
int ret3=search2(ida,idb+1);
int res=mymax(ret1,ret2,ret3);
dp[ida][idb]=res;
return res;
}
}
自底向上的求dp，写成动归格式的代码：
//动规
int search3(int ida,int idb){
//init dp 最下边的一行和最右边的一行
//初始化最下面一行
for(int j=len_b-1;j>=0;j--){
if(b[j]!=a[len_a-1]){
dp[len_a-1][j]=0;
}
else{
for(int k=0;k<=j;k++){
dp[len_a-1][k]=1;
}
break;
}
}
//初始化最右边一列
for(int i=len_a-1;i>=0;i--){
if(a[i]!=b[len_b-1]){
dp[i][len_b-1]=0;
}
else{
for(int k=0;k<=i;k++){
dp[k][len_b-1]=1;
}
break;
}
}
for(int i=len_a-2;i>=0;i--){
for(int j=len_b-2;j>=0;j--){
int ret1=-10000;
if(a[i]==b[j]){
ret1=dp[i+1][j+1]+1;
}
int ret2=dp[i+1][j];
int ret3=dp[i][j+1];
dp[i][j]=mymax(ret1,ret2,ret3);
}
}
return dp[0][0];
}
第一种解法虽然是正确的，but在lintcode上面一定是超时的。附上一个lintcode格式的代码：
//写成lintcode格式的代码
//www.lintcode.com/zh-cn/problem/longest-common-subsequence/
class Solution {
public:
/*
* @param A: A string
* @param B: A string
* @return: The length of longest common subsequence of A and B
*/
int mymax(int a,int b,int c){
int max_item1=max(a,b);
int max_item2=max(max_item1,c);
return max_item2;
}
int longestCommonSubsequence(string &A, string &B) {
// write your code here
int a_size=A.size();
int b_size=B.size();
int **dp=new int* [a_size];
for(int i=0;i<A.size();i++){
dp[i]=new int[b_size];
}
// -1
for(int i=0;i<A.size();i++){
for(int j=0;j<B.size();j++){
dp[i][j]=-1;
}
}
//dp
for(int j=B.size()-1;j>=0;j--){
if(B[j]!=A[A.size()-1]){
dp[A.size()-1][j]=0;
}
else{
for(int k=0;k<=j;k++){
dp[A.size()-1][k]=1;
}
break;
}
}
//初始化最右边一列
for(int i=A.size()-1;i>=0;i--){
if(A[i]!=B[B.size()-1]){
dp[i][B.size()-1]=0;
}
else{
for(int k=0;k<=i;k++){
dp[k][B.size()-1]=1;
}
break;
}
}
for(int i=A.size()-2;i>=0;i--){
for(int j=B.size()-2;j>=0;j--){
int ret1=-10000;
if(A[i]==B[j]){
ret1=dp[i+1][j+1]+1;
}
int ret2=dp[i+1][j];
int ret3=dp[i][j+1];
dp[i][j]=mymax(ret1,ret2,ret3);
}
}
return dp[0][0];
}
};
完整的源码 github ：
https://github.com/zhaozhengcoder/Algorithm
