最长的公共子序列
- dp数组含义
dp[i][j]：长度为[0, i - 1]的字符串text1与长度为[0, j - 1]的字符串text2的最长公共子序列为dp[i][j]（即前i个字符和前j个字符匹配） - 递推公式
当text1[i] == text2[j]
当前匹配的i和j是相同的字符，dp[i+1][j+1] = dp[i][j] + 1;
dp应该是不包括第i+1 和第j+1字符之前匹配成功个数+1
要把i+1和j+1让出来。
当text1[i] ！= text2[j]
当前匹配的i和j是不同的字符，dp[i+1][j+1] = max(dp[i+1][j],dp[i][j+1]);
dp为包括i+1字符或者包括j+1字符的最大值
当匹配成功时
为什么不是 dp[i+1][j+1] = max(dp[i+1][j],dp[i][j+1])+1;
因为会造成一个字母匹配多次
例如 text1中有一个b，text2中有两个b
在i+1为text1的b，j+1为text2中第二个b时：
max(dp[i+1][j],dp[i][j+1])包含和text2中第一个b匹配，+1是和第二个b匹配。
则造成了text1中字母b与text2中两个b分别匹配。
因此应该是dp[i+1][j+1] = dp[i][j] + 1，这样让开要匹配的字符
class Solution { public: int longestCommonSubsequence(string text1, string text2) { vector<vector<int>> dp(text1.size()+1 , vector<int>(text2.size()+1 ,0) ); for(int i=0 ;i<text1.size();i++) { for(int j=0; j<text2.size();j++) { if(text1[i] == text2[j]) dp[i+1][j+1] = dp[i][j] + 1; else dp[i+1][j+1] = max(dp[i+1][j],dp[i][j+1]); } } // for(int i=0 ;i<=text1.size();i++) // { // for(int j=0; j<=text2.size();j++) // { // cout<<dp[i][j]<<' '; // } // cout<<endl; // } return dp[text1.size()][text2.size()]; } };
二刷
class Solution { public: int longestCommonSubsequence(string text1, string text2) { vector<vector<int>> dp(text1.size()+1 , vector<int>(text2.size()+1 ,0)); for(int i=0 ; i<text1.size() ; i++) { for(int j=0 ; j<text2.size() ; j++) { if(text1[i]==text2[j]) dp[i+1][j+1] = dp[i][j] + 1; else dp[i+1][j+1] = max(dp[i][j+1] , dp[i+1][j]) ; // cout<<dp[i+1][j+1]<<' '; } // cout<<endl; } return dp[text1.size()][text2.size()]; } };
