这个问题需要借鉴到动态规划中非常典型的：最大公共子序列问题的算法
【问题描述】
两种水果杂交出一种新水果，现在给新水果取名，要求这个名字中包含了以前两种水果名字的字母，并且这个名字要尽量短。也就是说以前的一种水果名字arr1是新水果名字arr的子序列，另一种水果名字arr2也是新水果名字arr的子序列。设计一个算法求arr。
例如：输入以下3组水果名称：
apple peach
ananas banana
pear peach
输出的新水果名称如下：
appleach
bananas
pearch
【提示】
本题目的思路是先求 arr1 和 arr2 字符串的最长公共子序列，基本过程参见《教程》第8章8.5节，再利用递归输出新水果取名。
算法中设置二维动态规划数组dp，dp[i][j]表示arr1[0..i-1]（i个字母）和arr2[0..j-1]（j个字母）中最长公共子序列的长度。另外设置二维数组b，b[i][j]表示arr1和arr2比较的3种情况：
b[i][j]=0表示arr1[i-1]=arr2[j-1]；
b[i][j]=1表示arr1[i-1]≠arr2[j-1]并且dp[i-1][j]>dp[i][j-1]；
b[i][j]=2表示arr1[i-1]≠arr2[j-1]并且dp[i-1][j]≤dp[i][j-1]。
【主要算法框架】
void main( ) {
int t; //输入测试用例个数
printf("测试用例个数: ");
scanf("%d",&t);
while(t--) {
scanf("%s",arr1);
scanf("%s",arr2);
memset(b,-1,sizeof(b));
m=strlen(arr1); //m为arr1的长度
n=strlen(arr2); //n为arr2的长度
LCSlength( ); //求出dp, 并且给b[][]数组赋值
printf("结果: ");
Output(m,n); //输出新水果取名
printf("\n");
} 文章来源：https://www.toymoban.com/news/detail-492830.html
}
void Output(int i, int j){ //利用递归输出新水果取名
if (i==0 && j==0) //输出完毕
return;
if(i==0) { //arr1完毕，输出arr2的剩余部分
Output(i,j-1);
printf("%c",arr2[j-1]);
return;
}
else if(j==0) { //arr2完毕，输出arr1的剩余部分
Output(i-1,j);
printf("%c",arr1[i-1]);
return;
}
if (b[i][j]==0) { //arr1[i-1]=arr2[j-1]的情况
Output(i-1,j-1);
printf("%c",arr1[i-1]);
return;
}
else if(b[i][j]==1) {
Output(i-1,j);
printf("%c",arr1[i-1]);
return;
}
else{
Output(i,j-1);
printf("%c",arr2[j-1]);
return;
}
}
源代码部分：文章来源地址https://www.toymoban.com/news/detail-492830.html
#include<bits/stdc++.h>
using namespace std;
#define MAX 51 //序列中最多的字符个数
//问题表示
int m,n;
string a,b; //求解结果表示
int dp[MAX][MAX]; //动态规划数组
int bs[MAX][MAX];
vector<char> subs; //存放LCS
void LCSlength() //求dp
{ int i,j;
for (i=0;i<=m;i++) //将dp[i][0]置为0，边界条件
dp[i][0]=0;
for (j=0;j<=n;j++) //将dp[0][j]置为0，边界条件
dp[0][j]=0;
for (i=1;i<=m;i++)
for (j=1;j<=n;j++) //两重for循环处理a、b的所有字符
{ if (a[i-1]==b[j-1]){
dp[i][j]=dp[i-1][j-1]+1;
bs[i][j]=0;
}
else{
dp[i][j]=max(dp[i][j-1],dp[i-1][j]);
if(dp[i-1][j]>dp[i][j-1]) bs[i][j]=1;
else bs[i][j]=2;
}
}
}
void output(int i,int j){
if(i==0 && j==0) return;
if(i==0){
output(i,j-1); cout<<b[j-1]; return;
}
else if(j==0){
output(i-1,j); cout<<a[i-1]; return;
}
if(bs[i][j]==0){
output(i-1,j-1);cout<<a[i-1];return;
}
else if(bs[i][j]==1){
output(i-1,j);cout<<a[i-1];return;
}
else{
output(i,j-1);cout<<b[j-1];return;
}
}
int main(){
cin>>a>>b;
m=a.length();n=b.length();
LCSlength();
output(m,n);
return 0;
}到了这里，关于算法动态规划之杂交水果取名问题的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
