力扣1143、1035、53打卡第三十五天

1143. 最长公共子序列

最重要的点，也是想不通的点在于如何处理不连续的问题，也就是dp[ i ] [ j ]的状态不知源于dp[ i-1 ] [ j-1 ]同时也源于dp[ i-1 ] [ j ]和dp[ i ] [ j-1 ]这是关键，代码如下：

    public int longestCommonSubsequence(String text1, String text2) {
        int re=0;
        int[][] dp = new int[text1.length()+1][text2.length()+1];
        for(int i=1;i<=text1.length();i++){
            for(int j=1;j<=text2.length();j++){
                if(text1.charAt(i-1)==text2.charAt(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]);
                }
                if(re<dp[i][j])re = dp[i][j];
            }
        }
        return re;
    }

1035. 不相交的线

和上一题一模一样，嗯直接上代码：

    public int maxUncrossedLines(int[] nums1, int[] nums2) {
        int re=0;
        int[][] dp = new int[nums1.length+1][nums2.length+1];
        for(int i=1;i<=nums1.length;i++){
            for(int j=1;j<=nums2.length;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]);
                }
                if(re<dp[i][j])re = dp[i][j];
            }
        }
        return re;
    }

53. 最大子数组和

用贪心做过一遍，这次用动态规划，其实原理是一样的，判断是否大于0，如果小于0那么直接用当前的值，如果大于零就加上后边的值，最后取一个最大的即可代码如下：

    public int maxSubArray(int[] nums) {
        int[] dp = new int[nums.length];
        int res = nums[0];
        dp[0] = nums[0];
        for(int i=1;i<nums.length;i++){
            if(dp[i-1]<0)dp[i] = nums[i];
            else{
                dp[i] = dp[i-1] + nums[i];
            }
            res = dp[i]>res?dp[i]:res;
        }
        return res;
    }