LeetCode分类专题（五）——动态规划1-子序列

iwehdio的博客园：https://www.cnblogs.com/iwehdio/

学习自：

1、基本思路

  • 动态规划的基本思路是：当前状态的解可以由前几个状态的解计算而成，也就是所谓的状态转移方程。也就是分治（数学归纳法），逐渐降低问题的规模。

  • 在降低问题规模的过程中，可能会出现相同的问题，即所谓的重叠子问题。每个子问题都有一个确定的最优解，即最优子结构，这部分可以用一个dp表来优化。

  • 写出dp表，首先要对dp表中的位置dp[i][j]的含义做一个定义。

  • 在问题的规模达到最小，比如0或者1时，问题的答案是确定的，作为base case。

  • dp表的构建顺序是有规则的：

    1. 遍历的过程中，所需的状态必须是已经计算出来的。

    2. 遍历的终点必须是存储结果的那个位置。

  • 动态规划解题过程：

    1. 确定dp表以及下标的含义。
    2. 确定状态转移方程。
    3. 确定dp数组的初始化即base case。
    4. 确定遍历顺序。
    5. 距离推导dp数组。

  • 对于子序列问题而言：

    • 每次建立的dp数组比字符串规模大1，可以简化边界操作。
    • 每次都在尾部进行操作，因为尾部之前的操作已经在之前的比对中完成了。
    • 如果是子序列，dp数组的定义需要包括前一部分的最后一个元素。

2、子序列问题

  • 300 最长递增子序列

    image-20210306163944858

    • 在这里，dp[i]的定义是，以nums[i]为结尾的最长递增子序列的长度。
      • 这样定义的原因是，首先求解目的是最长递增子序列的长度。
      • 其次，只有知道了这个序列中的最大值，才能知道新值能不能添加到序列中。
    • 状态转移方程为：dp[i+1]等于符合nums[j]<nums[i]情况下（j<i），最大的dp[j]再加一。
    • base case为，子序列最少包含自己，即为1。
    class Solution {
    public int lengthOfLIS(int[] nums) {
        int[] dp = new int[nums.length];
        Arrays.fill(dp, 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);
                }
            }
        }
        int ans = 1;
        for(int i=0; i<dp.length; i++) {
            ans = Math.max(dp[i], ans);
        }
        return ans;
    }
}

  • 1143 最长公共子序列

    image-20210306184701281

    • 这里dp[i][j]的含义是，text1[0:i-1]和text2[0:j-1]的最长公共子序列的长度。
    • 状态转移方程是，比较第i-1个字符和第j-1个字符，如果相等那么dp[i][j] = 1 + dp[i-1][j-1]，否则dp[i][j] = Math.max(dp[i][j-1], dp[i-1])。
    • base case是，i或j为0时，一个字符串为空，长度为0。
    class Solution {
    
    public int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length(), n = text2.length();
        int[][] dp = new int[m+1][n+1];
        for(int i=1; i<=m; i++) {
            for(int j=1; j<=n; j++) {
                if(text1.charAt(i-1)==text2.charAt(j-1)) {
                    dp[i][j] = 1 + dp[i-1][j-1];
                } else {
                    dp[i][j] = Math.max(dp[i][j-1], dp[i-1][j]);
                }
            }
        } 
        return dp[m][n];
    }
}

  • 583 两个字符串的删除操作

    image-20210306185622130

    • 与上一道题类似，因为删除后留下的就是最长公共子序列。
    class Solution {
    public int minDistance(String word1, String word2) {
        int m=word1.length(), n=word2.length();
        int[][] dp = new int[m+1][n+1];
        for(int i=1; i<=m; i++) {
            for(int j=1; j<=n; j++) {
                if(word1.charAt(i-1)==word2.charAt(j-1)) {
                    dp[i][j] = 1+dp[i-1][j-1];
                } else {
                    dp[i][j] = Math.max(dp[i-1][j] , dp[i][j-1]);
                }
            }
        }
        return m+n-2*dp[m][n];
    }
}

  • 712 两个字符串的最小ASCII删除和

    image-20210306190543453

    • 与之前类似，只不过要求极值的不是长度而是ACSII码和，所以把状态转移方程改为ACSII码和即可。
    class Solution {
    public int minimumDeleteSum(String s1, String s2) {
        int m=s1.length(), n=s2.length();
        int[][] dp = new int[m+1][n+1];
        int sum = 0;
        for(int i=0; i<m; i++) {
            sum += s1.charAt(i);
        }
        for(int i=0; i<n; i++) {
            sum += s2.charAt(i);
        }
        for(int i=1; i<=m; i++) {
            for(int j=1; j<=n; j++) {
                if(s1.charAt(i-1)==s2.charAt(j-1)) {
                    dp[i][j] = dp[i-1][j-1] + s1.charAt(i-1);
                } else {
                    dp[i][j] = Math.max(dp[i][j-1] , dp[i-1][j]);
                }
            }
        }
        return sum - dp[m][n]*2;
    }
}

  • 5 最长回文子串

    image-20210306193923006

    • dp[i][j]数组的含义是，子串[i,j]是否是回文字符串。
    • base case初始化时注意初始化的是所有单个字符串或者两个连续的相同字符。
    • 状态转移方程是，根据新添加的子串和原来的做与运算。
    • 需要注意的是遍历方式，k的含义是i和j的差，初始化为2。
    class Solution {
    public String longestPalindrome(String s) {
        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        int lo=0, hi=0, max=0;
        for(int i=0; i<n; i++) dp[i][i]=true;
        for(int i=0; i<n-1; i++) {
            if(s.charAt(i+1)==s.charAt(i)) {
                dp[i][i+1]=true;
                lo=i;
                hi=i+1;
                max=1;
            }
        }
        for(int k=2; k<n; k++) {
            for(int i=0; i+k<n; i++) {
                int j=i+k;
                if(s.charAt(i)==s.charAt(j)) {
                    if(i==j || i+1==j) {
                        dp[i][j] = true;
                    } else {
                        dp[i][j] = dp[i+1][j-1];
                    }
                    if(dp[i][j] && j-i+1>max) {
                        lo=i;
                        hi=j;
                        max=j-i+1;
                    }
                } 
            }
        }
        return s.substring(lo, hi+1);
    }
}

  • 516 最长回文子序列

    image-20210306200415129

    • dp[i][j]数组的含义是，子串[i,j]中最长回文子序列的长度。
    • 如果s[i]与s[j]相等，那么dp[i][j] = dp[i+1][j-1] + 2，否则dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1])，即i和j起码不同时出现在最长回文子串中。
    class Solution {
    public int longestPalindromeSubseq(String s) {
        int n = s.length();
        int[][] dp = new int[n][n];
        for(int i=0; i<n; i++) {
            dp[i][i] = 1;
        }
        for(int k=1; k<n; k++) {
            for(int i=0; i+k<n; i++) {
                int j=i+k;
                if(s.charAt(i)==s.charAt(j)) {
                    dp[i][j] = dp[i+1][j-1] + 2;
                } else {
                    dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]);
                }
            }
        }
        return dp[0][n-1];
    }
}

  • 354 俄罗斯套娃信封问题

    image-20210306203156388

    • 需要先把信封按宽度升序排列，在宽度相同时，按照高度降序排列，然后求高度的最长递增序列的长度。

    • 宽度升序，高度降序，避免了相同宽度的重复判断。

      image-20210306203344074

    class Solution {
    public int maxEnvelopes(int[][] envelopes) {
        int n = envelopes.length;
        Arrays.sort(envelopes, new Comparator<int[]>(){
            public int compare(int[] a, int[] b) {
                return a[0]==b[0] ? b[1]-a[1] : a[0]-b[0];
            }
        });
        int[] height = new int[n];
        for(int i=0; i<n; i++) {
            height[i] = envelopes[i][1];
        }
        return lengthOfLIS(height);
    }
    public int lengthOfLIS(int[] nums) {
        int[] dp = new int[nums.length];
        Arrays.fill(dp, 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);
                }
            }
        }
        int ans = 1;
        for(int i=0; i<dp.length; i++) {
            ans = Math.max(dp[i], ans);
        }
        return ans;
    }
}

  • 72 编辑距离

    image-20210306210518651

    • 对A字符串的插入相当于对B字符串的删除，反之亦然。所以只剩下了三种操作：

      • 对A字符串插入。
      • 对B字符串插入。
      • 对A字符串替换。

    • 用 A = horse，B = ros 作为例子，来看一看是如何把这个问题转化为规模较小的若干子问题的。

      • 在单词 A 中插入一个字符：如果我们知道 horse 到 ro 的编辑距离为 a，那么显然 horse 到 ros 的编辑距离不会超过 a + 1。这是因为我们可以在 a 次操作后将 horse 和 ro 变为相同的字符串，只需要额外的 1 次操作，在单词 A 的末尾添加字符 s，就能在 a + 1 次操作后将 horse 和 ro 变为相同的字符串；
      • 在单词 B 中插入一个字符：如果我们知道 hors 到 ros 的编辑距离为 b，那么显然 horse 到 ros 的编辑距离不会超过 b + 1，原因同上；
      • 修改单词 A 的一个字符：如果我们知道 hors 到 ro 的编辑距离为 c，那么显然 horse 到 ros 的编辑距离不会超过 c + 1，原因同上。

    • 那么从 horse 变成 ros 的编辑距离应该为 min(a + 1, b + 1, c + 1)。

    class Solution {
    public int minDistance(String word1, String word2) {
        int m=word1.length(), n=word2.length();
        int[][] dp = new int[m+1][n+1];
        for(int i=0; i<=m; i++) {
            dp[i][0] = i;
        }
        for(int i=0; i<=n; i++) {
            dp[0][i] = i;
        }
        for(int i=1; i<=m; i++) {
            for(int j=1; j<=n; j++) {
                if(word1.charAt(i-1)==word2.charAt(j-1)) {
                    dp[i][j] = dp[i-1][j-1];
                } else {
                    dp[i][j] = Math.min(dp[i-1][j-1]+1, Math.min(dp[i][j-1]+1, dp[i-1][j]+1));
                }
            }
        }
        return dp[m][n];
    }
}

iwehdio的博客园：https://www.cnblogs.com/iwehdio/
来源与结束于否定之否定。
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/iwehdio/p/14492403.html