刷代码随想录有感（125）：动态规划——最长公共子序列

题干：

代码：

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 = 1; i <= text1.size(); i++){for(int j = 1; j <= text2.size(); j++){if(text1[i - 1] == text2[j - 1])dp[i][j] = dp[i - 1][j - 1] + 1;else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);}}return dp[text1.size()][text2.size()];}
};

递推公式：如果相同，则后一个为前一个长度加一；如果不相同(如图c不等于e)，情况一：考虑c不考虑e，则变成abc与ac的最长公共子序列，此时为dp[i][j-1]; 情况二：考虑e不考虑c，则变成ace与ab的最长公共子序列，此时为dp[i-1][j]。综上最后dp[i][j]取他们当中最大的一个。

定义：dp[i][[j]为以 i - 1和j - 1为结尾的最长公共子序列长度。