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

1143.最长公共子序列

完���

思路：

定义二维dp数组，dp[i][j]代表以i-1结尾的text1和以j-1结尾的text2 的最长公共子序列长度，动态规划求子序列的相关问题中，dp数组这样定义是为了规避复杂的初始化，这是一个技巧。

代码

dp[i][j]代表以i结尾的text1和以j结尾的text2 的最长公共子序列长度

class Solution {    public int longestCommonSubsequence(String text1, String text2) {        // dp[i][j]代表以i结尾的text1和以j结尾的text2 的最长公共子序列长度        int[][] dp = new int[text1.length()][text2.length()];        // 初始化开始--------------------------------------------------        // 需要初始化最上行和最左列        // 前面的元素为0，后一个元素需要比较得到；前面的元素为1，后一个元素一定是1        dp[0][0] = text1.charAt(0) == text2.charAt(0)?1:0;        int flag = dp[0][0];        for (int i = 1; i  
dp[i][j]代表以i-1结尾的text1和以j-1结尾的text2 的最长公共子序列长度
 
class Solution {    public int longestCommonSubsequence(String text1, String text2) {        // dp[i][j]代表以i-1结尾的text1和以j-1结尾的text2 的最长公共子序列长度        int[][] dp = new int[text1.length()+1][text2.length()+1];        for (int i = 1; i             for (int j = 1; j             // 注意这里不是 i 和 j                if(text1.charAt(i-1)==text2.charAt(j-1)) dp[i][j] = Math.max(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[text1.length()][text2.length()];    }}    public int maxUncrossedLines(int[] nums1, int[] nums2) {        int[][] dp = new int[nums1.length+1][nums2.length+1];        for (int i = 1; i             for (int j = 1; j                 if(nums1[i-1] == nums2[j-1]) 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[nums1.length][nums2.length];    }}    public int maxSubArray(int[] nums) {        // dp[i]代表以i结尾的数组中 最大子数组和        int[] dp = new int[nums.length];        dp[0] = nums[0];        int res = nums[0];        for (int i = 1; i