题目描述

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

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

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/qJnOS7
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路：

这个题目很明显是一个动态规划题，但是难点在于有两个字符串，需要在两个字符串之间比较，
那我们可以把这个转换成一个二维的动态规划问题，这个问题的特点我们来分析一下；

1.重叠子问题；
怎么去分解这个问题？字符串可以分解成一个个长度更短的子串，在这里就可以分解为”a”,”ab”,”abc”这种长度依次递增的子串间的公共子序列
但是因为有两个字符串，所以这个子问题从一维需要升为二维的子问题，也就是两个字符串长度依次递增然后寻找最长公共子序列长度的问题。
2.最优子结构；
那么这个问题是否具有最优子结构呢？答案显而易见，我当前找到的最长的公共子序列长度（可能会有几个同时长度一样的），但是其中之一必然构成之后更长的子序列的一部分。
3.状态转移方程
那怎么转移呢？下面这个图展示的比较清楚，但是要公式化描述的话可以这样：
image.png
image.png

解题代码

  1. class Solution {
  2. public:
  3.     int longestCommonSubsequence(string text1, string text2) {
  4.         int m = text1.length(), n = text2.length();
  5.         vector<vector<int>> dp(m + 1, vector<int>(n + 1));
  6.         for (int i = 1; i <= m; i++) {
  7.             char c1 = text1.at(i - 1);
  8.             for (int j = 1; j <= n; j++) {
  9.                 char c2 = text2.at(j - 1);
  10.                 if (c1 == c2) {
  11.                     dp[i][j] = dp[i - 1][j - 1] + 1;
  12.                 } else {
  13.                     dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
  14.                 }
  15.             }
  16.         }
  17.         return dp[m][n];
  18.     }
  19. };

这里代码设计的时候有一个小的细节，就是我dp的空间比字符串长度大1，这样可以有助于简化代码，便于处理第一层刚开始的情况。

时间空间复杂度分析

两层for循环 O(mn)
空间复杂度也是O（mn）级别的，因为开辟了一个二维的dp数组