织梦网站建设流程,晋中网站建设哪家强,微信导航网站怎么做,深圳网页设计有限公司2017-08-06 15:41:04 writer#xff1a;pprp 刚开始学dp#xff0c;集训的讲的很难#xff0c;但是还是得自己看#xff0c;从简单到难#xff0c;慢慢来#xff08;如果哪里有错误欢迎各位大佬指正#xff09; 题意如下#xff1a; 给两个字符串#xff0c;找到其中大…2017-08-06 15:41:04 writerpprp 刚开始学dp集训的讲的很难但是还是得自己看从简单到难慢慢来如果哪里有错误欢迎各位大佬指正 题意如下 给两个字符串找到其中大的公共子序列每个样例输出一个数 最长公共子串Longest Common Substirng和最长公共子序列Longest Common SubsequenceLCS的区别为 子串是串的一个连续的部分子序列则是从不改变序列的顺序而从序列中去掉任意的元素而获得新的序列 也就是说子串中字符的位置必须是连续的子序列则可以不必连续。 动态规划的思想abcfbc 和 abfcab找匹配值图是大佬画的借用一下^_^ 可以看出 状态的定义 当前匹配到某一位置时已经匹配的数目 状态转移设记录匹配状态的二维数组叫a[1001][1001] 如果str1[i] str2[j] 那么a[i][i] a[i-1][j-1] 1; 如果str1[i] ! str2[j] 那么a[i][j] max(a[i-1][j], a[i][j-1]); 状态结束 匹配完成 代码如下 #include iostream
#include string
#include cstringusing namespace std;int a[1001][1001];int _max(int a, int b)
{return a b ? a : b;
}int main()
{string str1,str2;while(cin str1 str2){int len1 str1.length();int len2 str2.length();memset(a,0,sizeof(a));for(int i 1 ; i len1 ; i){for(int j 1 ; j len2 ; j){if(str1[i-1] str2[j-1]){a[i][j] a[i-1][j-1] 1;}else{a[i][j] _max(a[i-1][j],a[i][j-1]);}}}cout a[len1][len2] endl;}return 0;
} 提交状态ac转载于:https://www.cnblogs.com/pprp/p/7295014.html
