代码随想录算法训练营第四十一天| 1143.最长公共子序列 1035.不相交的线 53. 最大子序和

Smartisan / 2023-08-02 / 原文

1143.最长公共子序列

要求：

可以跳过，找出来最长符合的节点

难点：

如何跳过了之后仍然保留之前的值

思路:

如果不符，并不是dp[i-1][j-2]等于之前的值，而是dp[i][j] 等于它的相关节点

以上很重要

代码：

 1 // 要求： 两个子数组，可以删减跳过，找出最长的长度
 2 // 思路：dp[n][m] 代表第n-1 m-1的重复长度
 3 // 因为个别字节可以跳过，不可以+1，再加一个数组
 4 // 遍历dp[n][m] = dp[n][m-1]
 5 // 
 6 // 可以删减，之前的思路：
 7 //    1，dp[n]以N为结尾，然后遍历0-n有没有一样的节点，然后放进去
 8 // 
 9 // 思路：
10 //    1，如果当前节点相等，那么找到上一个节点中最大的值，在后面+1
11 // 
12 // 新思路： （如何跳过节点）
13 // 如果不满足， dp[i][j] = max(dp[i-1][j],dp[i][j-1]) 向左和上，保持一致
14 //
15 int longestCommonSubsequence(string text1, string text2) {
16     int result = 0;
17 
18     vector<vector<int>> dp(text1.size() + 1, vector<int>(text2.size() + 1, 0));
19 
20     for (int i = 1; i <= text1.size(); i++)
21     {
22         for (int j = 1; j <= text2.size(); j++)
23         {
24             if (text1[i - 1] == text2[j - 1])
25             {
26                 dp[i][j] = dp[i - 1][j - 1] + 1;
27             }
28             else
29             {
30                 dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);
31             }
32 
33             result = result > dp[i][j] ? result : dp[i][j];
34         }
35     }
36 
37     return result;
38 }