子序列问题
子序列存在很多种可能，那么一共有多少种可能的子序列呢，每个字符或数都可以选和不选，所以一共有2的n次方种选择，暴力枚举肯定是要超时的，所以一般情况下都是采用动态规划来优化。
动态规划是集合的思想，一类转移到另一类来起到优化的 效果。

最长上升子序列
二维动态规划，
首先要搞清楚f[i] 的值都可能由哪些值递推过来
这道题里对于nums[i]， 前面每一个小于i的数 j 都可能做为 i为结尾的子序列的倒数第二个数。也就是前面每一个状态都可能是递推得到限制这个状态的前一个状态，然后找出所有的最值，就是当前状态的(往往求最值的动态规划都是这样，不仅仅由前面一个状态得到的，可能是前面好几个状态都能递推到这个状态，然后再求最值)
初始状态的定义
F[0]，以第0个数结尾的最长递增子序列长度就是1
所以f[0] = 1

优化
开始想到能不能维护一个值，这个值代表目前位置最大的值，但是这一个值是远远不够的，例如数组是 [1, 4, 2, 3] 当扫描到2时，目前最大值是4，但是 和这个4比较并不能快速得到最长的公共子序列，因为每一个数都可能当子序列的结尾，那么就要枚举每个数当结尾时候，能得到的最长子序列的长度，再进行比较。 1当结尾时的最长值，4当结尾时候，2当结尾时候，3当结尾时候。那么优化的思路就是能否对当前的数nums[i]，快速找到一个比他小的数 a， 并能够得到a的长度是多少。快速找到一个比他小的数，可以采用二分来找，这样做到 logN 的时间复杂度。那么怎么同时得到这个数a代表的长度是多少呢？ 用一个有序数组来表示，index代表了长度，value就是从左往右目前这个长度下的最小值是多少， 1.如果当前nums[i]比后一个小，那么要更新数组后一个元素的值。这里为什么要存下来最小值，因为当你存最小值，后面得到的如果比最小值大，那就可以形成一个上升的子序列。2. 当前nums[i]前面最小的数是这个数组的最后一位数，那么就要把nums[i] 加入到数组种。
这样一共扫描一遍，每次通过二分找比nums[i]小的值，一共是NlogN
二分的边界情况，统一处理不了可以特殊做判断处理，例如这道题要找第一个小于的数，那如果全部都大于等于，也就是list里的第一个数都大于等于，那就直接把第一个数替换成这个数nums[i]就可以了。

最长公共子序列
583. Delete Operation for Two Strings
这道题和编辑距离的区别在于，编辑距离是使得A能够变成B，而这道题是同时删除两个string里的元素，如何删除能够使得两个string一样，还是有区别的，编辑距离是删除一个，这道题是两个同时删除

最长回文子序列
516. Longest Palindromic Subsequence

也是采用动态规划来算
更像区间dp，要枚举长度， f[i][j]定义为第i个数到第j个数 最长回文子序列的长度，(如果是连续的就不用DP了，中心扩散法就可以解决).第一维先枚举区间长度，再枚举起点，那么终点就是区间长度加上起点

for(int len = 2; len <= n; len++ ){
    for(int i = 1; i + len - 1 <= n; i++){
        int j = i + len - 1;
        if(s.charAt(i - 1) == s.charAt(j - 1)) f[i][j] = f[i + 1][j - 1] + 2;
        else f[i][j] = Math.max(f[i][j - 1], f[i + 1][j]);
    }
}

最长回文子串，中心扩散法，分奇数偶数讨论
5. Longest Palindromic Substring
因为是连续子串，其实不用动态规划，采用双指针枚举就可以做，枚举中间点，从哪开始扩散，这里要注意扩散的时候要分为奇数和偶数进行讨论，如果是偶数长度的，有一个小技巧就是，枚举的是中间的前面的那个点，这样的话不会重复，也不会遗漏

class Solution {
    int maxLen = 0;
    int ori = 0;
    public String longestPalindrome(String s) {
        for(int i = 0; i < s.length(); i++){

            //for odd
            check(s, i, i);
            check(s, i, i + 1);

        }
        return s.substring(ori, ori + maxLen);
    }

    public void check(String s, int start, int end){
        int res = 0;
        while(start >= 0 && end < s.length() && s.charAt(start) == s.charAt(end)){
            start--;
            end++;
        }

        start++;
        end--;

        if(maxLen < end - start + 1){
            maxLen = end - start + 1;
            ori = start;
        }

    }

}

回文子串
647. Palindromic Substrings
也是回文子串，一样采用中心枚举法，然后进行奇数偶数的分别判断，这里也是 对于枚举偶数长度的时候，人为规定枚举前面的长度，然后后面的+1来取，这样可以保证不重不漏的枚举

class Solution {
    int res = 0;
    public int countSubstrings(String s) {
        for(int i = 0; i < s.length(); i++){

            for(int j = i, k = i; j >= 0 && k < s.length(); j--, k++){
                if(s.charAt(j) != s.charAt(k)) break;
                else res++;
            }

            for(int j = i, k = i + 1; j >= 0 && k < s.length(); j--, k++){
                if(s.charAt(j) != s.charAt(k)) break;
                else res++;
            }

        }
        return res;
    }
}

编辑距离问题

leetcode 53:
还是dp的思想，设f[n]数组表示以n为结尾之前最大的子序和
这题可以优化，把数组优化，用last存上一个位置的最大子序和

leetcode 152
用两个数组记录f[] g[] 分别为以i为结尾的最大值和最小值

subarray问题，如果必须是连续的subarray，
那么当求最大值时，枚举到index = i时，一定只有两种情况，和前面最大值连续的一定从某一个p加到i-1，再加上i
另一种情况就是i自己是最大值，这就是对于子数组最后一个数是index = i的最大子数组的情况
leetcode 1746，
重点就在于要把集合里各种情况枚举到了，别漏掉情况
设f[][] 数组，就是以i为结尾的subarray的最大值， f[i][0]，为到i为止都没进行过自乘操作
f[i][1]，为到i为止进行过自乘操作，这个自乘操作可以进行在 index = i 处，可以进行在 index = i之前
而对于f[i][1]也包括三种情况，前面的subarray和加上nums[i] * nums[i]是最大的， f[i - 1][1] + nums[i],或者是nums[i] * nums[i]，

leetcode 1143 最长公共子序列
https://leetcode-cn.com/problems/longest-common-subsequence/solution/yong-di-hui-fen-jie-lai-jie-shi-dong-tai-x4ox/
dfs思路 参照
LIS最大长度是LDS的个数
https://www.acwing.com/problem/content/189/

子序列问题分类参考 https://leetcode-cn.com/problems/longest-common-subsequence/solution/dai-ma-sui-xiang-lu-dai-ni-xue-tou-dpzi-zqa9q/
子序列 不连续
lc300， lc1143， lc1035
连续和不连续 有个不同点是，连续的 以这个点为结尾的 那如果这个点不成立，状态就跟这个点有关系，例如 第一个字符串是i， 第二个字符串是j，而不连续的子串，如果这个点不成立，他可以根据前面的状态变过来，可以有第一个点i匹配j - 1 以及前面的状态，那么j - 1就可以表示相应的状态，同理 j也可以匹配i - 1以及前面的状态
连续
设f[i] 为以i为结尾的子串的状态
lc 674，718， 53

编辑距离问题
lc392， 115， 583， 72

115
最后一步统计选不选S[i]，编辑距离一般都是看最后一步，长的字符串最后一个选还是不选

583可以转化成最长公共子序列问题
392是双指针问题，判断子序列，用双指针来判断

回文串问题
lc647， 516, 5
516 区间dp问题，第一维先枚举区间长度，再枚举起点，那么终点就是区间长度加上起点
516题又是可以用DP或者记忆化搜索来解题
记忆化搜索就是对暴力枚举的优化剪枝，动态规划是集合的思想递推
对于子序列的问题，一般暴力枚举的都是start指针，和end指针，递归枚举下一层状态指针指哪
记忆化搜索做法

class Solution {
    int[][] memo;
    public int longestPalindromeSubseq(String s) {
        int n = s.length();
        memo = new int[n][n];
        for(int i = 0; i < n; i++){
            Arrays.fill(memo[i], -1);
        }
        return helper(s, 0, n - 1);
    }

    public int helper(String s, int start, int end){
        if(memo[start][end] != -1) return memo[start][end];
        if(start == end ) return 1;
        if(start > end ) return 0;
        if(s.charAt(start) == s.charAt(end)){
            memo[start][end] = helper(s, start + 1, end - 1) + 2;
            return memo[start][end];
        }else{
            memo[start][end] = Math.max(helper(s, start + 1, end), helper(s, start, end - 1));
            return memo[start][end];
        } 
    }
}

动态规划

class Solution {
    public int longestPalindromeSubseq(String s) {
        int n = s.length();
        int[][] f = new int[n][n];

        for(int i = 0; i < n; i++){
            f[i][i] = 1;
        }

        for(int len = 2; len <= n; len++ ){
            for(int i = 0; i + len - 1 < n; i++){
                int j = i + len - 1;
                if(s.charAt(i) == s.charAt(j)) f[i][j] = f[i + 1][j - 1] + 2;
                else f[i][j] = Math.max(f[i + 1][j], f[i][j - 1]);
            }
        }
        return f[0][n - 1];
    }
}

字符串问题，dp 情况讨论 好多都是以i j在不在来讨论，一共四种情况