dp-最长公共子序列以及dp-最长公共子串

class Solution { public: int longestCommonSubsequence(string text1, string text2) { //定义0到i-1的text1以及0到j-1的text2的最长公共子序列为dp[i][j]; int dp[1001][1001]; int len1=text1.size(); int len2=text2.size(); for(int i=1;i<=len1;i++)//根据定义来 for(int j=1;j<=len2;j++) if(text1[i-1]==text2[j-1])dp[i][j]=dp[i-1][j-1]+1;//相等肯定代表最长公共能+1 else{//如果不等肯定要根据前面的来，可能是dp[i][j-1]或者dp[i-1][j]; dp[i][j]=max(dp[i][j-1],dp[i-1][j]); } return dp[len1][len2]; } };

重新做了一次，没写出来！ 思路

class LongestSubstring { public: int findLongest(string A, int n, string B, int m) { // write code here int dp[1001][1001]={0}; int ans=0; for(int i=0;i<n;i++) for(int j=0;j<m;j++){ if(A[i]==B[j]){ dp[i][j]=dp[i-1][j-1]+1; ans=max(ans,dp[i][j]); } } return ans; } };

思路 把二维数组列出来，定义dp[i][j]为是否刚好有以0到i结尾和0到j结尾的公共子串，所以最后的答案不会在dp[i][j]中。