动态规划|【动态规划】最长公共子序列（LCS）动态规划|动态规划

文章图片

文章图片

【动态规划|【动态规划】最长公共子序列（LCS）】
文章图片

#include #include using namespace std; char A[1010]; char B[1010]; int dp[1010][1010]; int main(){ //从1开始存储,处理边界 gets(A+1); gets(B+1); int m=strlen(A+1); //注意从A+1开始存的 int n=strlen(B+1); //相等:两边都取,(i-1号位置和j-1号位置)+1 //dp[i][j]=dp[i-1][j-1]+1 //不相等:不确定i,j哪个长 //dp[i][j]=max(dp[i-1][j],dp[i][j-1])for(int j=0; j<=n; j++){ dp[0][j]=0; } for(int i=0; i<=m; i++){ dp[i][0]=0; }for(int i=1; i<=m; i++){ for(int j=1; j<=n; 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]; } } }printf("%d",dp[m][n]); return 0; }