子序列动态规划编程题集合（leetcode)

给定字符串 s 和 t ，判断 s 是否为 t 的子序列。

字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，”ace”是”abcde”的一个子序列，而”aec”不是）。

 public boolean isSubsequence(String s, String t) {
        int m=s.length(),n=t.length();
        //dp数组表示s中以i-1为结尾的字符串和t中以j-1为结尾的字符串的公共子序列的长度，若最右下角的数值等于m字符串的长度则说明为子序列
        //if s.charAt(i-1)==t.charAt(j-1) dp[i][j]=dp[i-1][j-1]+1; else  dp[i][j]=dp[i][j-1];
        int[][] dp=new int[m+1][n+1];
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                if(s.charAt(i-1)==t.charAt(j-1))
                    dp[i][j]=dp[i-1][j-1]+1;
                else
                    dp[i][j]=dp[i][j-1];
            }
        }
        return dp[m][n]==m;
    }

贪心算法

我们初始化两个指针 ii 和 jj，分别指向 ss 和 tt 的初始位置。每次贪心地匹配，匹配成功则 ii 和 jj 同时右移，匹配 ss 的下一个位置，匹配失败则 jj 右移，ii 不变，尝试用 tt 的下一个字符匹配 ss。最终如果 ii 移动到 ss 的末尾，就说明 ss 是 tt 的子序列。

 public boolean isSubsequence(String s, String t) {
        int n = s.length(), m = t.length();
        int i = 0, j = 0;
        while (i < n && j < m) {
            if (s.charAt(i) == t.charAt(j)) {
                i++;
            }
            j++;
        }
        return i == n;
    }

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

示例 1：

输入：nums = [10,9,2,5,3,7,101,18]

输出：4

 public static int com(int[] nums){
        //关键是遍历数组中的每个点，一每个点作为子序列的最后 结尾，然后二次循环从前往后寻找最大的子序列长度
       int[] dp=new int[nums.length];
       for(int i=0;i<dp.length;i++)
           dp[i]=1;
       for(int j=1;j<dp.length;j++){
           int max=0;
           for(int i=0;i<j;i++){
               if(nums[i]<nums[j]){
                   max=Math.max(max,dp[i]);
               }
           }
           dp[j]=dp[j]+max;
       }
       return Arrays.stream(dp).max().getAsInt();
 
    }

给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

例如，“ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。

若这两个字符串没有公共子序列，则返回 0。

示例 1:

输入：text1 = “abcde”, text2 = “ace”

输出：3

解释：最长公共子序列是 “ace”，它的长度为 3。

最长公共子序列和第一题求判断子序列类似

给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。

子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。


输入：s = “bbbab” 输出：4 解释：一个可能的最长回文子序列为 “bbbb” 。

引用官方图片

class Solution {
    public int longestPalindromeSubseq(String s) {
        int n = s.length();
        int[][] dp = new int[n][n];
        for (int i = n - 1; i >= 0; i--) {
            dp[i][i] = 1;
            char c1 = s.charAt(i);
            for (int j = i + 1; j < n; j++) {
                char c2 = s.charAt(j);
                if (c1 == c2) {
                    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];
    }
}

给定两个单词 word1 和 word2 ，返回使得 word1 和 word2 相同所需的最小步数。

每步 可以删除任意一个字符串中的一个字符。

输入: word1 = “sea”, word2 = “eat”

输出: 2

解释: 第一步将 “sea” 变为 “ea” ，第二步将 “eat “变为 “ea”

 public int minDistance(String word1, String word2) {        int[][] dp=new int[word1.length()+1][word2.length()+1];        for(int i=1;i<dp.length;i++){            for(int j=1;j<dp[0].length;j++){                if(word1.charAt(i-1)==word2.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]);            }        }        int i = word2.length() + word1.length() - 2 * dp[word1.length()][word2.length()];        return i;    }