最长公共子序列

题意回顾

给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

• 例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。
  两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

解决

动态规划的经典问题，首先我们要明确dp数组的含义

我们定义 dp[1005][1005]，那么 dp[i][j] 指的是text1中前i个字符和text2中前j个字符的最长公共子序列的长度

那么如何递推dp呢？

这里有三个方向，一个是 i-1,j-1，一个是 i-1, j，一个是 i,j-1
我们从上往下，从左往右推

如果 text1[i] == text2[j]，那么当前的公共子序列的长度就从之前的结果递推过来加一
否则从 i-1, j，i,j-1 里面取一个最大值，这两个方向不同的地方在于：
去掉text1的当前一个 或 去掉 text2的当前一个，可以获得最长的长度

代码

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int dp[1005][1005];
        for (int i = 0; i < text1.size(); i++) {
            for (int j = 0; j < text2.size(); j++) {
                dp[i][j] = 0;
                if (text1[i] == text2[j]) {
                    dp[i][j] = (i && j) ? dp[i-1][j-1]+1 : 1;
                } else {
                    if (j && dp[i][j-1] > dp[i][j]) dp[i][j] = dp[i][j-1];
                    if (i && dp[i-1][j] > dp[i][j]) dp[i][j] = dp[i-1][j];
                }
            }
        }
        return dp[text1.size()-1][text2.size()-1];
    }
};