动态规划之子序列问题 大多是需要二维动态规划的

遍历顺序大多是从上往下从左往右，特别的回文子串和最长回文子序列，是从下往上。

300.最⻓递增⼦序列

class Solution {
  public int lengthOfLIS(int[] nums) {
        if(nums.length == 0) return 0;
        int[] dp = new int[nums.length];
        int res = 0;
        Arrays.fill(dp, 1);// 默认是1 
        for(int i = 0; i < nums.length; i++) {
            for(int j = 0; j < i; j++) {
                if(nums[j] < nums[i]) dp[i] = Math.max(dp[i], dp[j] + 1);
            }
            res = Math.max(res, dp[i]);
        }
        return res;
    }


}

674. 最⻓连续递增序列

贪心

class Solution {
    public int findLengthOfLCIS(int[] nums) {
        int res = 1, max = 1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] > nums[i - 1]) {
                res++;
            } else {
                res = 1;
            }
            max = Math.max(max, res);
        }
        return max;
    }
}

基于本题贪心的思路，可以联想到LeetCode原题： 122. 买卖股票的最佳时机 II，贪心的思路为：因为交易次数不受限，我们可以把所有的上坡全部收集到，然后求和，其结果一定是利益最大化

作者：ju-ren-zhang
链接：https://leetcode-cn.com/problems/longest-continuous-increasing-subsequence/solution/tu-biao-si-lu-kan-bu-dong-ni-da-wo-ji-ba-7fr7/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

动态规划：

class Solution {
    public int findLengthOfLCIS(int[] nums) {
        int[] dp = new int[nums.length];
        Arrays.fill(dp, 1);
        int res = 1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] > nums[i - 1]) {
                dp[i] = dp[i - 1] + 1;
            }
            res = Math.max(res, dp[i]);
        }   
        return res;
    }
}

718. 最⻓重复⼦数组

class Solution {
    public int findLength(int[] nums1, int[] nums2) {
        int n = nums1.length;
        int m = nums2.length;
        int[][] dp = new int[n + 1][m + 1]; // dp[i][j]表示A的前i项与B的前j项的最长重复子数组长度
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (nums1[i - 1] == nums2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    ans = Math.max(ans,dp[i][j]);
                }
            }
        }
        return ans;
    }
}

1143.最⻓公共⼦序列

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int n1 = text1.length(),n2 = text2.length();
        int[][] dp = new int[n1+1][n2+1];
        for (int i = 1; i <= n1; i++) {
            for (int j = 1; j <= n2; j++) {
                char c1 = text1.charAt(i-1);
                char c2 = text2.charAt(j-1);
                dp[i][j] = c1==c2 ? dp[i-1][j-1]+1 : Math.max(dp[i-1][j],dp[i][j-1]);
            }
        }
        return dp[n1][n2];
    }
}

53. 最⼤⼦序和

class Solution {
    public int maxSubArray(int[] nums) {
        // if(nums==null||nums.length==0)return null;
        if(nums.length==1)return nums[0];
        int pre = nums[0];
        int max = Integer.MIN_VALUE;
        max = Math.max(max,pre);
        
        for (int i = 1; i < nums.length; i++) {
            pre = Math.max(nums[i],nums[i]+pre);
            // i依次增加  pre会依次变成以对应位置结尾的子序列和的最大值
            // max存储 所有位置序列和的最大值
            max = Math.max(max,pre);
        }
        return max;
    }
}

392.判断⼦序列

这道题⽬算是编辑距离的⼊⻔题⽬（毕竟这⾥只是涉及到减法），也是动态规划解决的经典题型。

可以用双指针来做

class Solution {
    public boolean isSubsequence(String s, String t) {
        int slen = s.length(), tlen = t.length();
        if(slen>tlen) return false;
        if(slen==0)return true;
        int sptr = 0, tptr = 0;
        while(tptr<tlen){
            if(t.charAt(tptr)==s.charAt(sptr) && (++sptr==slen)) {
                return true;
            }
            tptr++;
        }
        return false;
    }
}

动态规划也可