当前位置：首页 > news >正文

LeeCode Practice Journal | Day44_DP11 子序列问题

news 来源：原创 2024/9/19 16:10:49

1143. 最长公共子序列

题目：1143. 最长公共子序列 - 力扣（LeetCode）
题解：代码随想录 (programmercarl.com)

solution

public class Solution {public int LongestCommonSubsequence(string text1, string text2) {int m = text1.Length;int n = text2.Length;   int[,] dp = new int[m,n];int result = 0;for(int i = 0; i < m; i++){for(int j = 0; j < n; j ++){if(i == 0 && j == 0) dp[0,0] = text1[0] == text2[0] ? 1 : 0;else if(i == 0) dp[0, j] = text1[0] == text2[j] ? 1 : dp[0, j - 1];else if(j == 0) dp[i, 0] = text1[i] == text2[0] ? 1 : dp[i - 1, 0];else{if(text1[i] == text2[j]) dp[i, j] = dp[i-1,j-1] + 1;else dp[i,j] = Math.Max(dp[i-1, j], dp[i, j-1]); }result = Math.Max(result, dp[i,j]);}}return result;}
}

summary

错误：

1、思路：
dp[i,j] : 以text1[ i ]，text2[ j ]结尾的？？？很奇怪的思路

dp：

1、dp[ i ][ j ]：text1 0-i 子串和text2 0-j 子串的最长公共子序列

2、递推：
text1[ i ] == text2[ j ]：dp[ i-1 ][ j-1 ] + 1
text1[ i ] != text2[ j ]：Math.Max(dp[ i ][ j-1 ] , dp[ i-1 ][ j ])

3、初始化
初始化第一行和第一列

1035. 不相交的线

题目：1035. 不相交的线 - 力扣（LeetCode）
题解：代码随想录 (programmercarl.com)
和上题完全一致

solution

public class Solution {public int MaxUncrossedLines(int[] nums1, int[] nums2) {int m = nums1.Length;int n = nums2.Length;   int[,] dp = new int[m,n];int result = 0;for(int i = 0; i < m; i++){for(int j = 0; j < n; j ++){if(i == 0 && j == 0) dp[0,0] = nums1[0] == nums2[0] ? 1 : 0;else if(i == 0) dp[0, j] = nums1[0] == nums2[j] ? 1 : dp[0, j - 1];else if(j == 0) dp[i, 0] = nums1[i] == nums2[0] ? 1 : dp[i - 1, 0];else{if(nums1[i] == nums2[j]) dp[i, j] = dp[i-1,j-1] + 1;else dp[i,j] = Math.Max(dp[i-1, j], dp[i, j-1]); }result = Math.Max(result, dp[i,j]);}}return result;}
}

53. 最大子序和

题目：53. 最大子数组和 - 力扣（LeetCode）
题解：代码随想录 (programmercarl.com)

solution

public class Solution {public int MaxSubArray(int[] nums){int n = nums.Length;int[,] dp = new int[n,2];dp[0,0] = nums[0];dp[0,1] = nums[0];for(int i = 1; i < n; i ++){dp[i, 0] = Math.Max(dp[i-1, 0], dp[i-1, 1]);dp[i, 1] = Math.Max(dp[i-1, 1] + nums[i], nums[i]);}return Math.Max(dp[n-1,0], dp[n-1,1]);}
}

summary

dp：

1、dp数组
dp[ i ，0 ]：0-i 子串不包含nums[ i ] 的最大子序和
dp[ i ，1 ]：0-i 子串包含nums[ i ] 的最大子序和

2、递推：
dp[i, 0] = Math.Max(dp[i-1, 0], dp[i-1, 1]);
dp[i, 1] = Math.Max(dp[i-1, 1] + nums[i], nums[i]);

3、初始化：（错误）
dp[0,1] 和 dp[0,0]都要初始化为第一个元素

392. 判断子序列

题目：392. 判断子序列 - 力扣（LeetCode）
题解：代码随想录 (programmercarl.com)
还是最长公共子序列的变体

solution

public class Solution {public bool IsSubsequence(string s, string t) {int m = t.Length;int n = s.Length;if(n == 0) return true;if(m == 0) return false;int[,] dp  = new int[m, n];for(int i = 0; i < m; i ++){for(int j = 0; j < n; j ++){if(i == 0 && j == 0) dp[0,0] = t[i] == s[j] ? 1 : 0;else if(i == 0 && j != 0) dp[0,j] = t[0] == s[j] ? 1 : dp[0, j-1];else if(j == 0 && i != 0) dp[i,0] = t[i] == s[0] ? 1 : dp[i-1, 0];else{if(t[i] == s[j]) dp[i,j] = dp[i-1, j-1] + 1;else dp[i,j] = Math.Max(dp[i-1, j], dp[i, j-1]);}}}return dp[m-1, n-1] == s.Length;}
}