求最长公共子序列的长度

• （对我自己说的） dp打表的原因就是为了避免子问题重复计算,而递归多次重复计算(斐波那契)
• 最优子结构：每一个子问题都要通过上一步递推得到该状态下的最优解,且不会影响到后面的问题

1. 既然求长度且长度要最优,用dp来表示某个状态下的长度
2. 如何表示某个状态下的长度,我也想不到
3. 字符串a,b，一维数组肯定不行,用dp[i][j]表示a中[1,i]的子字符串 和 b中[1,j]子字符串的最长公共子序列的长度

• 状态方程如何表示？

1. 当a[i] == b[j]时，此时最大长度为 分别以i-1 j-1结尾的子串的最大长度+1
2. a[i] != b[j] 这一状态的最大长度不会改变(因为不相同), 要要继承上一个状态中的长度最大值(最长),(子问题 要 满足 最优解),那么从上一个状态推过来(延续过来)为 dp[i][j] = max(dp[i-1][j],dp[i][j-1])
3. 为什么dp[i][j] != max{dp[i-1][j],dp[i][j-1],dp[i-1][j-1]},为什么状态转移方程里面不包括dp[i-1][j-1]呢？我们退回到dp[i][j-1]这一步来看,dp[i-1][j] = max(dp[i-2][j],dp[i-1][j-1]),此时dp[i-1][j-1]已经被计算过一次，所以即使状态方程+上 dp[i-1][j-1],只是重复计算了而已，并不影响最优解(我自己的看法,)

   #include <stdio.h>
   #include <string.h>
   const int maxn = 1e3+10;
   char a[maxn];
   char b[maxn];
   int dp[maxn][maxn];
   int main() {
   //	freopen("a.txt","r",stdin);
   	while (  scanf("%s",a+1) != EOF && scanf("%s",b+1) != EOF ) {
   		memset(dp,0,sizeof dp);
   		int alen = strlen(a+1);
   		int blen = strlen(b+1);
   		dp[alen][0] = 0;
   		dp[0][blen] = 0;
   		
   		for (int i=1; i<=alen; i++) {
   			for (int j=1; j<=blen; j++) {
   				if (a[i] == b[j]) {
   					dp[i][j] = dp[i-1][j-1]+1;
   					
   				}
   				else dp[i][j] = dp[i-1][j]>dp[i][j-1] ? dp[i-1][j] : dp[i][j-1];					
   			}
   		}
   //		cout << dp[alen][blen] << endl;
   		printf("%d\n",dp[alen][blen]);
   	}
   	return 0;
   }

   求最长公共子序列

• 先lcs()把二维dp[][]表打出来,然后根据表从 dp[i][j] 倒推最长公共子序列
• 为什么要倒着推？可能想到试一试从dp[0][0]开始推，因为现在dp[][]已经是所有情况的状态空间,如果正这推，根据dp[][]表，根本推不出来(除非dfs再次搜索一遍)

倒着找公共子序列

1. a[i]==b[j]，记录并且回到a[i-1] b[j-1]即dp[i-1][j-1]
2. a[i] != b[j],此时根据dp表存的最大长度,往值大的方向走,因为值大的方向包括更多的相同的单个字符，那么会走遍最长的公共子序列
3. 因为dp[i][j] = max(dp[i-1][j],dp[i][j-1]),只选择长度相同的一方,所以另一个就被忽视掉了,最后推的也只是所有LCS中的一个

#include <iostream>
#include <string.h>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

const int maxn = 1e3+10;

int dp[maxn][maxn];
char a[maxn];
char b[maxn];

void lcs() {
	memset(dp,0,sizeof dp);
	int alen = strlen(a+1);
	int blen = strlen(b+1);

	//确定dp的范围条件 
	
	dp[alen][0] = 0; //a全都有,b为空
	dp[0][blen] = 0; //b全都有,a为空

	

	for (int i=1; i<=alen; i++) {
		for (int j=1; j<=blen; j++) {
			if (a[i] == b[j]) 
				dp[i][j] = dp[i-1][j-1] + 1; 
			else 
				dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
		}
	}
}

void stringlcs(int alen,int blen) { //根据打出来的表 来求 公共串
	string ans;
	int i = alen;
	int j = blen;

	while ( i!=0 && j!=0 ) {
		if (a[i] == b[j]) {
			ans += a[i];
			i--;
			j--;
		}
		//往左上方走的时候尽量走大的，因为他们有相同的字符
		else if (dp[i][j-1] < dp[i-1][j]) {
			i--;
		}
		else if (dp[i][j-1] >= dp[i-1][j]) {
			j--;
		}
	}
	reverse(ans.begin(),ans.end());
	cout << ans  << endl;
}

int main() {
//	freopen("a.txt","r",stdin);
	while (scanf("%s",a+1) != EOF && scanf("%s",b+1) != EOF) {
		lcs();
		int alen = strlen(a+1);
		int blen = strlen(b+1);
		stringlcs(alen,blen);
	}
	return 0;
}