动态规划之LCS最长子序列问题

#include <iostream>
#include <string>
using namespace std;

int max(int a, int b)
{
	if(a > b)
		return a;
	else
		return b;
}

/**
简单递归方法：只满足最优子结构，但重叠子问题重复计算
*/
//m,n is the length of string a,b
int lcs1(string &a, string &b, int m, int n)
{
	if(m == 0 || n == 0)
		return 0;
	if(a[m-1] == b[n-1])
		return lcs1(a, b, m-1, n-1) + 1;
	else
		return max(lcs1(a,b,m-1,n), lcs1(a,b,m,n-1));
}

/**
优化重叠子问题的效率晋升为动态规划的算法
*/
int table[10][10] = {(0,0)};//全部初始化为0的table数组用于存储子问题结果
int lcs2(string &a, string &b, int m, int n)
{
	if(m == 0 || n == 0)
		return 0;
	if(table[m][n] != 0)
		return table[m][n];
	if(a[m-1] == b[n-1])
		table[m][n] = lcs2(a, b, m-1, n-1) + 1;
	else
		table[m][n] = max(lcs2(a,b,m-1,n), lcs2(a,b,m,n-1));
	return table[m][n];
}

/**
同时记录lcs以便最后输出最长子序列
*/
string temp = ""; //全局string用于不断加成lcs
int lcs3(string &a, string &b, int m, int n)
{
	if(m == 0 || n == 0)
		return 0;
	if(a[m-1] == b[n-1])
	{
		temp += a[m-1];
		return lcs3(a, b, m-1, n-1) + 1;
	}
	else
		return max(lcs3(a,b,m-1,n), lcs3(a,b,m,n-1));
}

int main()
{
	string a = "BACDAB";
	string b = "ADACB";
	cout<<lcs3(a,b,a.length(),b.length())<<endl;
	cout<<temp<<endl;

	return 0;
}
#include <iostream>
#include <string>
usi