POJ 1458 longest common subsequence (dynamic planning exercise)

Catalog

Dynamic planning details

Example POJ 1458

Dynamic planning details

Hanging memory recursive dynamic programming （ With example explanation POJ 1163）_m0_62044244 The blog of -CSDN Blog Memory recursive dynamic programming method I ： recursive （ Time consuming #include<iostream>#include<algorithm>using namespace std;#define MAX 101const int N=1e7+10;int MAXsum(int i,int j);int n;int a[MAX][MAX];int main(){cin>>n;int i,j;for(i=1;i&lhttps://blog.csdn.net/m0_62044244/article/details/123143714?spm=1001.2014.3001.5501

Example POJ 1458

1458 -- Common Subsequencehttp://poj.org/problem?id=1458

 

#include<iostream>
#include<cstring>
using namespace std;
#define MAX 1000
const int N=1e7+10;
char a[1000],b[1000];
int maxlen[MAX][MAX];
int main()
{
	int i,j;
	while(cin>>a>>b)
	{
		int l1=strlen(a);
		int l2=strlen(b);
		for(i=0,j=0;j<=l2;j++)
		{
				maxlen[i][j]=0;
		}
		for(i=0,j=0;i<=l1;i++)
		{
				maxlen[i][j]=0;
		}
		for(i=1;i<=l1;i++)
		{
			for(j=1;j<=l2;j++)
			{
				if(a[i-1]==b[j-1])
					maxlen[i][j]=maxlen[i-1][j-1]+1;
				else
					maxlen[i][j]=max(maxlen[i-1][j],maxlen[i][j-1]);
			}
		}
		cout<<maxlen[l1][l2]<<endl;
	}
	return 0;
}