最大公共子序列问题：就是两个字符串相似的最大子符长度！！！。
这个问题关键还是在于把子问题与原问题的桥梁求出来：
如上式中，当x
i =y
j 于是就有
否则：
于是结合以上两种情况便可得出代码：
#ifndef MAX_LENGTHCOMMSUBSTR_H#define MAX_LENGTHCOMMSUBSTR_H#define max(a,b) a>b? a:bint maxLengthComSubSTR(char *a_array,char *b_array,int a_index,int b_index){ if(a_index==0||b_index==0){ return 0; } if(a_array[a_index-1]==b_array[b_index-1]){ return maxLengthComSubSTR(a_array,b_array,a_index-1,b_index-1)+1; }else{ return max(maxLengthComSubSTR(a_array,b_array,a_index-1,b_index),maxLengthComSubSTR(a_array,b_array,a_index,b_index-1)); }}#endif
测试代码：
int main(){ char *str1="BDCABA"; char *str2="ABCBDAB"; std::cout<<maxLengthComSubSTR(str1,str2,6,7)<<std::endl; }
来自为知笔记(Wiz)
转载于:https://www.cnblogs.com/yml435/p/4655534.html
相关资源：最长公共子序列_动态规划
