LCR 095. 最长公共子序列（C语言+动态规划）

1. 题目

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

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

        例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。

        两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

2. 输入输出样例

        示例 1：

输入：text1 = "abcde", text2 = "ace" 
输出：3  
解释：最长公共子序列是 "ace" ，它的长度为 3 

        示例 2： 

输入：text1 = "abc", text2 = "abc"
输出：3
解释：最长公共子序列是 "abc" ，它的长度为 3 

         示例 3：

输入：text1 = "abc", text2 = "def"
输出：0
解释：两个字符串没有公共子序列，返回 0 。

 提示：

• 1 <= text1.length, text2.length <= 1000
• text1 和 text2 仅由小写英文字符组成。

3. 解题思想

        动态规划步骤：

        （1）dp状态：

                dp[i][j]表示以text1[i]、text2[j]为结尾的两个字符串中最长公共子序列的长度；

        （2）状态转移方程：

                text1[i] == text2[j]：dp[i][j] = dp[i - 1][j - 1] + 1;

                text1[i] != text2[j]：max(dp[i - 1][j], dp[i][j - 1]);

        （3）初始化状态：

                第0行第0列：text1[0] == text2[0]：dp[0][0] = 1；text1[0] != text2[0]：dp[0][0] = 0;

                第0行：text1[i] == text2[0]：dp[i][0] = 1；text1[i] != text2[0]：dp[i][0] = dp[i - 1][0];

                第0列：text1[0] == text2[i]：dp[0][1] = 1；text1[0] != text2[i]：dp[0][i] = dp[0][i-1];

         （4）最优解：

                dp[n-1][m-1] ；

        算法描述：

        核心思想是通过填充 dp 数组，逐步构建最长公共子序列的长度，考虑字符是否匹配。

• 首先，获取输入字符串 text1 和 text2 的长度，并创建一个二维数组 dp，其大小为 (n+1) x (m+1)，其中 n 和 m 分别是两个字符串的长度。dp[i][j] 表示 text1 的前 i 个字符和 text2 的前 j 个字符的最长公共子序列的长度。
• 初始化 dp 数组的第一行和第一列：遍历两个字符串的首字符，如果它们相等，将 dp[0][0] 设置为1，否则将其保留为0。接着，初始化第一行和第一列的其余部分，以表示以 text1[0] 或 text2[0] 开头的子序列。
• 使用两个嵌套循环遍历 text1 和 text2 的每个字符（除去第一个字符），填充 dp 数组。如果当前字符相同（text1[i] == text2[j]），则将 dp[i][j] 设置为左上角的对角元素值加1，表示找到了一个更长的公共子序列。如果当前字符不同，将 dp[i][j] 设置为左边或上边的较大值，表示要么继承左边的最长子序列长度，要么继承上边的最长子序列长度。
• 最终，dp[n-1][m-1] 中存储的值即为 text1 和 text2 的最长公共子序列的长度。

4. 代码实现

// 定义一个函数，该函数返回两个整数指针中的较大值
int max_(int *a, int *b) {// 比较两个指针的值，返回较大的指针if (a > b) {return a;}return b;
}// 定义一个计算两个字符串的最长公共子序列的函数
int longestCommonSubsequence(char *text1, char *text2) {// 获取字符串text1和text2的长度int n = strlen(text1);int m = strlen(text2);// 创建一个二维数组dp，用于存储最长公共子序列的长度int dp[n][m];// 初始化dp数组，将所有元素设置为0for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {dp[i][j] = 0;}}// 初始化dp数组的第一个元素if (text1[0] == text2[0]) {dp[0][0] = 1;}// 处理第一列，初始化以text1[0]为开头的子序列for (int i = 1; i < n; i++) {if (text1[i] == text2[0]) {dp[i][0] = 1;} else {dp[i][0] = dp[i - 1][0];}}// 处理第一行，初始化以text2[0]为开头的子序列for (int i = 1; i < m; i++) {if (text1[0] == text2[i]) {dp[0][i] = 1;} else {dp[0][i] = dp[0][i - 1];}}// 填充dp数组的其余部分，找到最长公共子序列的长度for (int i = 1; i < n; i++) {for (int j = 1; j < m; j++) {if (text1[i] == text2[j]) {// 如果字符相同，将dp[i][j]设置为左上角值加1dp[i][j] = dp[i - 1][j - 1] + 1;} else {// 如果字符不相同，将dp[i][j]设置为左边和上边的较大值dp[i][j] = max_(dp[i - 1][j], dp[i][j - 1]);}}}// 返回dp数组的最右下角元素，即最长公共子序列的长度return dp[n - 1][m - 1];
}

 5. 复杂度分析

        时间复杂度分析：

• 初始化 dp 数组的两个嵌套循环（for 循环嵌套）需要遍历整个数组，时间复杂度为O(n * m)，其中 n 和 m 分别是 text1 和 text2 的长度。
• 接下来，还需要一个嵌套循环来填充 dp 数组，这个循环也需要遍历整个 dp 数组，时间复杂度为O(n * m)。
• 总的时间复杂度是O(n * m + n * m)，即O(n * m)。

        算法的时间复杂度是 O(n * m)，其中 n 和 m 分别是输入字符串 text1 和 text2 的长度。

        

        空间复杂度分析：

• dp 数组的空间复杂度是O(n * m)，因为它是一个二维数组，其大小与输入字符串的长度相关。

综上所述，这段代码的空间复杂度是 O(n * m)，时间复杂度是 O(n * m)

 力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台https://leetcode.cn/problems/qJnOS7/submissions/