序列DP专题

1.最长递增子序列（LIS问题）

LC1713. 得到子序列的最少操作次数

这道题提供提供了一种时间复杂度为O(NlogN) 的方法求解最长递增子序列的长度

public int minOperations(int[] target, int[] arr) {
    /*
        从最长公共子序列问题(LCS)转化为最长递增子序列(LIS)问题
        如:target = [6,4,8,1,3,2], arr = [4,7,6,2,3,8,6,1]
        映射到map后:[6->0,4->1,8->2,1->3,3->4,2->5]
        则arr的索引为:[1,-1,0,5,4,2,0,3] 可以将-1去掉得到 [1,0,5,4,2,0,3]
        变相就是求映射后的arr最长严格递增子序列长度,最后答案是target长度-arr最长递增子序列长度
        由于arr范围在1e5 因此用O(N^2)办法必定TLE
        尝试维护一个数组minTail[i]记录长度为i的递增子序列结尾的最小数字
        显然minTail是单调递增的,因为递增序列长度越大,其最小结尾数字必然越大
        此时可以用二分加速搜索f[i]前面的最佳转移项f[j],f[j]必定满足条件:结尾数值<list[i]并且长度最大
        我们寻找结尾元素<list[i]的最大长度项,即结尾元素<list[i]的最大minIdx索引
        注意:
        1.这是边遍历list[i]边更新minTail[i],因此都是list[i]前面的索引
        2.由于LCS是没有重复元素的因此转化为LIS问题后是严格递增的
         */
    int m = target.length;
    HashMap<Integer, Integer> map = new HashMap<>();
    // 将target元素及索引映射到map
    for (int i = 0; i < m; i++) {
        map.put(target[i], i);
    }
    // 存储arr在target中的有效索引
    List<Integer> list = new ArrayList<>();
    for (int num : arr) {
        if (map.containsKey(num)) list.add(map.get(num));
    }
    // 此时问题转化为求list中最长严格递增子序列长度
    int n = list.size(), max = 0;   // max维护当前遍历的最长递增子序列长度(list可能为空因此max初始化为0)
    // f[i]为以list[i]结尾的最长递增子序列长度,minTail[i]为长度为i的递增子序列对应的最小结尾数字
    int[] f = new int[n], minTail = new int[n + 1];
    Arrays.fill(minTail, 0x3f3f3f3f); // 便于min比较得出最小索引
    // 遍历list
    for (int i = 0; i < n; i++) {
        // 记t为list[i]
        int t = list.get(i);
        // 二分查找minTail[i]<list[i]的最大数字
        int l = 0, r = i;   // 二分的是minTail的索引(递增子序列的长度)
        while (l < r) {
            int mid = l + (r - l + 1) / 2;
            if (minTail[mid] < t) {
                // 1.minTail[mid] < t说明mid也可能是正确答案
                l = mid;
            } else {
                // 2.minTail[mid] >= t说明mid不可能是正确答案
                r = mid - 1;
            }
        }
        // l == r 此时l为合法f[j]的最大长度,拼接上list[i]就是l+1
        f[i] = l + 1;
        // 更新max
        max = Math.max(max, f[i]);
        // 根据当前结尾数字更新minTail(记得是t,因为自始至终比较的是序列结尾数字t)
        minTail[f[i]] = Math.min(minTail[f[i]], t);
    }
    // 最少要插入的次数=target长度-最长递增子序列长度max
    return m - max;
}

模板1：基于LC300. 最长递增子序列

public int lengthOfLIS(int[] nums) {
    /*
    根据 1713. 得到子序列的最少操作次数
    这里给出一种时间复杂度为O(NlogN)的dp+贪心+二分解法
    1 <= nums.length <= 2500
    -1e4 <= nums[i] <= 1e4
    定义minTail[len]为当前遍历到的长度为len的递增子序列的最小结尾数字
    可知minTail[i]必定是单增的,我们可以用二分寻找到f[i]之前一个能拼接的最长的f[j]
    最后维护最大的f[i]就是答案
     */
    int n = nums.length, max = 1;
    int[] minTail = new int[n + 1];
    Arrays.fill(minTail, 0x3f3f3f3f);
    for (int i = 0; i < n; i++) {
        int l = 0, r = i;
        while (l < r) {
            int mid = l + (r - l + 1) / 2;
            if (minTail[mid] < nums[i]) {
                l = mid;
            } else {
                r = mid - 1;
            }
        }
        int cur = l + 1;
        max = Math.max(max, cur);
        minTail[cur] = Math.min(minTail[cur], nums[i]);
    }
    return max;
}

模板2：（效率更高）基于LC354. 俄罗斯套娃信封问题

public int maxEnvelopes(int[][] envelopes) {
    /*
    排序+序列DP+贪心:
    1 <= envelopes.length <= 1e5
    envelopes[i].length == 2
    1 <= wi, hi <= 105
    注意到数量范围:我们只能用O(N)或者O(logN)的方法进行解决
    1.首先对envelopes按照第一维度升序,第二维度降序进行排序
    2.然后我们找到第二维度的严格上升序列的最大长度就是答案
    证明:因为这样在第二维度取到的严格上升序列必定不是在第一维度相等的
    局部最优的贪心思路:顺序遍历num=envelopes[i][1]
    1.当遇到>结尾元素时,直接加入结尾
    2.当遇到<=结尾元素时,查找首个>=num的坑位用num取代
    总体时间复杂度:O(NlogN) 空间负复杂度:O(N
     */
    int n = envelopes.length;
    Arrays.sort(envelopes, (a, b) -> a[0] == b[0] ? b[1] - a[1] : a[0] - b[0]);
    // tails[i]表示以长度为i+1的结尾最小数字(必定递增)
    int[] tails = new int[n];
    tails[0] = envelopes[0][1];
    int end = 0;    // tails结尾索引指针
    for (int i = 1; i < n; i++) {
        // num大于结尾元素 -> 直接加入并偏移end指针
        int num = envelopes[i][1];
        if (num > tails[end]) {
            tails[++end] = num;
        } else {
            // 二分查找适合的插入位置(即寻找首个>=num的坑位)
            int l = 0, r = end;
            while (l < r) {
                int mid = l + (r - l) / 2;
                if (tails[mid] < num) { // 注意是对坑位索引进行二分查找
                    l = mid + 1;
                } else {
                    r = mid;
                }
            }
            // l == r
            tails[l] = num;
        }
    }
    // end最后表示最长递增子序列的索引,end+1就是长度(所求)
    return end + 1;
}

LIS的O(NlogN)解法压缩至求3元递增子序列

LC334. 递增的三元子序列

class Solution {
    public boolean increasingTriplet(int[] nums) {
        /*
        LIS问题拓展(贪心)：
        我们知道求解LIS问题除了有O(N^2)的方法外，还有一种可以加速至O(NlogN)的方法
        利用辅助数组minNum，其中minNum[len]为长度为len的递增子序列结尾最小数字
        但是我们这里是求3元子序列，只需要维护最长递增子序列最前面两个即可，因此可以直接在O(1)时间内找到前面可以拼接的数字
        时间复杂度:O(N) 空间复杂度:O(1)
         */
        // first为长度为1的递增子序列最小结尾数字，second为长度为1的递增子序列最小结尾数字
        int first = Integer.MAX_VALUE, second = Integer.MAX_VALUE;
        for (int num : nums) {
            if (num > second) return true;  // num可以拼接在原来的second后说明已经找到3元递增子序列
            // 维护first与second的值
            if (num < first) {
                first = num;    // 1.num最小，必然长度为1最小的就是num
            } else if (first < num && num < second) {
                second = num;   // 2.first < num说明num可以拼接在first后，再加上nums<second说明最小数字这个位置num可以取代原来的second
            }
        }
        // 最后都找不到
        return false;
    }
}

2.最长公共子序列（LCS问题）

最常规的DP转移方程就不说了，我们由此引出常见的问题模型：判断是否s1是否为s2子串

方法1：双指针->O(max(m,n))

写法1：

// 判断s1是否为s2子序列,是则返回true
private boolean check(String s1, String s2) {
    // 双指针实现
    int len1 = s1.length(), len2 = s2.length();
    int p1 = 0, p2 = 0;
    // p1主动移动且每次移动1格,p2被动移动
    while (p1 <= len1 - 1 && p2 <= len2 - 1) {
        // p2被动移动至与s1[p1]==s2[p2]的位置
        while (p2 <= len2 - 1 && s1.charAt(p1) != s2.charAt(p2)) {
            p2++;
        }
        if (p2 == len2) break;  // p2提前结束了就直接结束不要移动p1
        // 共同后移
        p1++;
        p2++;
    }
    // 退出的位置为s1最后一个待匹配的位置,p1指针刚好移出就表明s1是s2子串
    return p1 == len1;
}

写法2：

// 判断s1是否为s2子序列
private boolean match(String s1, String s2) {
    int len1 = s1.length(), len2 = s2.length();
    int p1 = 0, p2 = 0;
    while (p1 < len1 && p2 < len2) {
        // s2[p2]一直寻找直至与s1[p1]匹配
        while (p2 < len2 && s2.charAt(p2) != s1.charAt(p1)) p2++;
        if (p2 < len2) {
            // p1每次主动移动一位(p2匹配上了才移动)
            p1++;
            // p2也要移动
            p2++;
        }
    }
    return p1 == len1;  // p1==len1说明p1最后一位也匹配到p2有效值，p1==len1退出，说明s1是s2子串
}

方法2：DP->O(m*n)

// 最长公共子序列方法求解(LCS问题)
private boolean check(String s1, String s2) {
    int len1 = s1.length(), len2 = s2.length();
    int[][] f = new int[len1 + 1][len2 + 1];    // f[i][j]表示考虑s1[0,i-1]与s2[0,j-1]最长公共子序列长度
    for (int i = 1; i <= len1; i++) {
        for (int j = 1; j <= len2; j++) {
            // 考虑s1[i - 1]与s2[j - 1]是否相等来分类转移
            if (s1.charAt(i - 1) == s2.charAt(j - 1)) { // 1.相等直接转移
                f[i][j] = f[i - 1][j - 1] + 1;
            } else {    // 2.不相等其中有一个必定不能取,但是另外一个可能可以
                f[i][j] = Math.max(f[i - 1][j], f[i][j - 1]);
            }
        }
    }
    return f[len1][len2] == len1;
}

3.回文子串、子序列问题

最长回文子序列问题(非连续)

LC1312. 让字符串成为回文串的最少插入次数

class Solution {
    public int minInsertions(String s) {
        /*
        序列DP：最长回文子序列
        这题要求让s成为回文串的 最少插入次数，反过来就是求s原本有的最长回文子序列长度
        然后再插入与非回文字符数相等的字符即可
        1.状态定义:f[i][j]代表考虑s[i,j]最长回文子序列长度
        2.状态转移:要求f[i][j]就要比较s[i]与s[j]的值
            2.1 s[i]==s[j] 两个字母都要了，回文长度+2 f[i][j]=f[i+1][j-1]+2
            2.2 s[i]!=s[j] 两个字母最多只能保留一个，f[i][j]=max(f[i+1][j],f[i][j-1])
        3.初始化:f[i][i]=1，其余为0
        4.遍历顺序:i倒序，j正序 && i<j
        5.返回形式:n-f[0][n-1]
         */
        int n = s.length();
        int[][] f = new int[n][n];
        for (int i = 0; i < n; i++) {
            f[i][i] = 1;
        }
        for (int i = n - 2; i >= 0; i--) {
            for (int j = i + 1; j < n; j++) {
                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 n - f[0][n - 1];
    }
}

最长回文子串问题(连续)

LC647. 回文子串

class Solution {
    public int countSubstrings(String s) {
        /*
        1.状态定义:dp[i][j]表示s[i,j]之间是否回文,回文则为true(i<=j)
        2.状态转移:考虑s[i]与s[j]
            2.1 如果s[i]!=s[j] 说明s[i,j]必定不回文->不转移
            2.2 如果s[i]==s[j] 那就要看s[i+1,j-1]是否回文
                2.2.1 若j-i+1<=3即j-i<=2时必定回文 dp[i][j]=true
                2.2.2 j-i>2且dp[i+1][j-1]==true也是回文的 dp[i][j]=true
                2.2.3 j-i>2且dp[i+1][j-1]==false必定不回文的 -> 不转移
        3.初始化:左下角->右上角 无需初始化 后序推导会有j-i<=2的情况做铺垫
        4.遍历顺序:先i后j,i倒序,j无所谓
        5.返回形式:返回dp[i][j]中true的个数
         */
        int len = s.length();
        int res = 0;
        boolean[][] dp = new boolean[len][len];
        for (int i = len - 1; i >= 0; i--) {
            for (int j = i; j <= len - 1; j++) {
                // 1.s[i]!=s[j]
                if (s.charAt(i) != s.charAt(j)) {
                    continue;
                }
                // 2.s[i]==s[j]
                if (j - i <= 2) {
                    dp[i][j] = true;
                    res++;
                    continue;
                }
                // 3.s[i]==s[j] && j-i>2
                if (dp[i + 1][j - 1]) {
                    dp[i][j] = true;
                    res++;
                }
            }
        }
        return res;
    }
}

LC5. 最长回文子串

class Solution {
    public String longestPalindrome(String s) {
        /*
        1.状态定义:boolean类型的dp[i][j]表示s[i,j]之间的是否为回文串,其中i<=j
        2.状态转移:要想推断dp[i][j]即s[i,j]否为回文串,关键看s[i]与s[j]以及中间的dp[i+1][j-1]
            2.1 若s[i]!=s[j] 直接断定不是回文串(不转移)
            2.2 若s[i]==s[j] 并且中间是回文串:dp[i+1][j-1]==true 或者 j-i+1<=3 是回文串
        3.初始化:dp[i][j]=true,i==j
        4.遍历顺序:左下->右上 因此i必须倒序,j无所谓
        5.返回形式:维护最大长度回文串并返回:max(j-i+1) && dp[i][j]==true->s[i,j]
         */
        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        int maxLen = 1;
        int[] range = new int[]{0, 0};
        for (int i = n - 1; i >= 0; i--) {
            for (int j = n - 1; j >= i; j--) {
                // s[i]==s[j]的情况
                if (s.charAt(i) == s.charAt(j)) {
                    // 长度<=3或者中间也是回文
                    if (j - i <= 2 || dp[i + 1][j - 1]) {
                        // 转移
                        dp[i][j] = true;
                        // 更新最大长度与范围
                        if (j - i + 1 > maxLen) {
                            maxLen = j - i + 1;
                            range = new int[]{i, j};
                        }
                    }
                }
            }
        }
        // 截取s[i,j]
        return s.substring(range[0], range[1] + 1);
    }
}