C++动态规划之最长公子序列实例
本文实例讲述了C++动态规划之最长公子序列解决方法。分享给大家供大家参考。具体分析如下：
问题描述：
求出两个字符串中的最长公子序列的长度。
输入：
csblog
belong
输出：
maxlength=4
实现代码：
#include<stdio.h>
#include<string.h>
intarr[200][200];
/*表示str1的前i位和str2的前j位的最长公子序列的长度*/
intmain()
{
charstr1[100],str2[100];
/*输入数据*/
scanf("%s%s",str1,str2);
intlen1=strlen(str1);
intlen2=strlen(str2);
/*初始化数组*/
inti,j;
for(i=0;i<=len1;++i)
{
for(j=0;j<=len2;++j)
arr[i][j]=0;
}
/*计算*/
for(i=1;i<=len1;++i)
{
for(j=1;j<=len2;++j)
{
/*字符相同，则最长公子序列长度加1*/
if(str1[i-1]==str2[j-1])
{
arr[i][j]=arr[i-1][j-1]+1;
}
else
/*当前字符不相同，则取上次选择的最大值做为当前结果*/
{
arr[i][j]=arr[i][j-1]>arr[i-1][j]?arr[i][j-1]:arr[i-1][j];
}
}
}
/*输出结果*/
printf("maxlength=%d\n",arr[len1][len2]);
return0;
}
希望本文所述对大家的C++程序设计有所帮助。