Day47 算法记录|动态规划14子序列-Toy模板网

这篇具有很好参考价值的文章主要介绍了Day47 算法记录|动态规划14子序列。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

1143. 最长公共子序列

这道题和718. 最长重复子数组的区别：这道题的子序列可以不连续
Day47 算法记录|动态规划14子序列,算法,动态规划这个视频讲解的很好

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
     char[] A = text1.toCharArray();
     char[] B = text2.toCharArray();

     int[][] dp = new int[A.length+1][B.length+1];
     for(int i=1;i<=A.length;i++){
         for(int j =1; j<=B.length;j++){
             if(A[i-1] == B[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[A.length][B.length];

    }
}

1035.不相交的线

和上面一道题一摸一样
以绘制连接两个数字 A[i] 和 B[j] 的直线，只要 A[i] == B[j]，且直线不与任何其他连线（非水平线）相交。
Day47 算法记录|动态规划14子序列,算法,动态规划

class Solution {
    public int maxUncrossedLines(int[] A, int[] B) {
    
    int[][] dp = new int[A.length+1][B.length+1];
    for(int i=1;i<=A.length;i++){
        for(int j=1;j<=B.length;j++){
            if(A[i-1] == B[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[A.length][B.length];

    }
}

53. 最大子数组和

讲解的很好的一个
$d p [i]$ 表示包括下标i（以nums[i]为结尾）的最大连续子序列和为dp[i]。
$d p [i]$ 取决于 $d p [i - 1]$ 以及nums[i],所以，如果全为正数的化
（1）dp[i-1]<0，不能加，dp[i] =nums[i] （2）dp[i-1]>0，dp[i] =dp[i-1] + nums[i]

class Solution {
    public int maxSubArray(int[] nums) {
     int[] dp = new int[nums.length];
     dp[0] = nums[0];
     int res =dp[0];

     for(int i=1;i<nums.length;i++){
         dp[i] = nums[i] + (dp[i-1]<0?0:dp[i-1]);
         res = Math.max(dp[i],res);
     }
     return res;
    }
}

改进：因为 $d p [i]$ 只与 $d p [i - 1$ 有关文章来源地址https://www.toymoban.com/news/detail-617962.html

class Solution {
    public int maxSubArray(int[] nums) {
    
    int sum = nums[0];
     int res = nums[0];

     for(int i=1;i<nums.length;i++){
         sum = nums[i] + (sum<0?0:sum);
         res = Math.max(sum,res);
     }
     return res;
    }
}