两个数组的动态规划——最长公共子序列模型-Toy模板网

这篇具有很好参考价值的文章主要介绍了两个数组的动态规划——最长公共子序列模型。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

✅ tips

1.考虑空串，即dp表多出一行一列，代表某个字符串为空。

2.考虑最后一个位置；是否相等；

3.可在字符串最前面加虚拟位置以对应映射关系；

4.一般横行是j，列是i。此时第一行代表第二个字符串不为空，即第一个字符串是空的

1.最长公共子序列

class Solution {
    //dp[i][j]表s1的[0,i]以及s2的[0,j]所有子序列中最长公共子序列的长度；
    //如果s[i]=s[j]，那公共序列一定是以i,j为结尾
    public int longestCommonSubsequence(String s1, String s2) {
        int m = s1.length(), n = s2.length();
        s1 = " " + s1;
        s2 = " " + s2;
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (s1.charAt(i) == s2.charAt(j)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[m][n];
    }
}
//!=时，有[0,i-1]&[0,j],[0,i-1]&[0,j-1],[0,i]&[0,j-1];空串

        StringBuilder sb = new StringBuilder();
        int i = m, j = n;
        while (i > 0 && j > 0) {
            if (s1.charAt(i) == s2.charAt(j)) {
                sb.insert(0, s1.charAt(i));
                i--;
                j--;
            } else if (dp[i - 1][j] >= dp[i][j - 1]) {
                i--;
            } else {
                j--;
            }
        }

        System.out.println( sb.toString());

2.最长重复子数组

class Solution {
    public int findLength(int[] nums1, int[] nums2) {
        int m=nums1.length;int n=nums2.length;
        int[][] dp=new int[m+1][n+1];
        int ret=0;
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                if(nums1[i-1]==nums2[j-1])
                    dp[i][j]=dp[i-1][j-1]+1;
            
            ret=Math.max(ret,dp[i][j]);
            }
        }
        return ret;

    }
}

class Solution {
    public int[] findLength(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        int[][] dp = new int[m + 1][n + 1];
        int maxLength = 0;
        int endIndex = 0;
        
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (nums1[i - 1] == nums2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    if (dp[i][j] > maxLength) {
                        maxLength = dp[i][j];
                        endIndex = i - 1; // 结束索引
                    }
                }
            }
        }
        
        int[] result = new int[maxLength];
        for (int i = endIndex - maxLength + 1; i <= endIndex; i++) {
            result[i - (endIndex - maxLength + 1)] = nums1[i];
        }
        
        return result;
    }
}

class Solution {
    public int[] findLength(int[] nums1, int[] nums2) {
        int maxLength = 0;
        int endIndex = -1;
        
        for (int i = 0; i < nums1.length; i++) {
            for (int j = 0; j < nums2.length; j++) {
                int len = 0;
                while (i + len < nums1.length && j + len < nums2.length && nums1[i + len] == nums2[j + len]) {
                    len++;
                }
                
                if (len > maxLength) {
                    maxLength = len;
                    endIndex = i + maxLength - 1; 
                }
            }
        }
        
        int[] result = new int[maxLength];
        for (int i = endIndex - maxLength + 1; i <= endIndex; i++) {
            result[i - (endIndex - maxLength + 1)] = nums1[i];
        }
        
        return result;
    }
}

3.不同的子序列

给你两个字符串 s 和 t ，统计并返回在 s 的 子序列 中 t 出现的个数，结果需要对 109 + 7 取模。

示例 1：
输入：s = "rabbbit", t = "rabbit"
输出：3
解释：
如下所示, 有 3 种可以从 s 中得到 "rabbit" 的方案。
rabbbit
rabbbit
rabbbit

class Solution {
    //dp[i][j]在s的[0,j]的子序列中出现t的[0,i]子串的个数
    //是否包含字符s[j]
   public int numDistinct(String s, String t) {
        int m = t.length(), n = s.length();
        int[][] dp = new int[m + 1][n + 1];
        for (int j = 0; j <= n; j++) {
            dp[0][j] = 1;
        }
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j] = dp[i][j - 1];
                if (t.charAt(i - 1) == s.charAt(j - 1)) {
                    dp[i][j] += dp[i - 1][j - 1];
                }
            }
        }
        return dp[m][n];
    }
}

4.交错字符串

给定三个字符串 s1、s2、s3，请你帮忙验证 s3 是否是由 s1 和 s2 交错组成的。

两个字符串 s 和 t 交错的定义与过程如下，其中每个字符串都会被分割成若干非空子字符串：

s = s1 + s2 + ... + sn

t = t1 + t2 + ... + tm

|n - m| <= 1

交错是 s1 + t1 + s2 + t2 + s3 + t3 + ... 或者 t1 + s1 + t2 + s2 + t3 + s3 + ...

注意：a + b 意味着字符串 a 和 b 连接。

示例 1：
输入：s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
输出：true
示例 2：
输入：s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
输出：false
示例 3：
输入：s1 = "", s2 = "", s3 = ""
输出：true
提示：

0 <= s1.length, s2.length <= 100

0 <= s3.length <= 200

s1、s2、和 s3 都由小写英文字母组成

class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        int m = s1.length(), n = s2.length();
        if (m + n != s3.length()) {
            return false;
        }
        
        s1 = "" + s1;
        s2 = "" + s2;
        s3 = "" + s3;
        
        boolean[][] dp = new boolean[m + 1][n + 1];
        dp[0][0] = true; // 初始化第一个位置
        
        for (int j = 1; j <= n; j++) { // 初始化第一行
            if (s2.charAt(j - 1) == s3.charAt(j - 1)) {
                dp[0][j] = true;
            } else {
                break;
            }
        }
        
        for (int i = 1; i <= m; i++) { // 初始化第一列
            if (s1.charAt(i - 1) == s3.charAt(i - 1)) {
                dp[i][0] = true;
            } else {
                break;
            }
        }
        
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j] = (s1.charAt(i - 1) == s3.charAt(i + j - 1) && dp[i - 1][j])
                        || (s2.charAt(j - 1) == s3.charAt(i + j - 1) && dp[i][j - 1]);
            }
        }
        
        return dp[m][n];
    }
}

5.通配符匹配

44. 通配符匹配https://leetcode.cn/problems/wildcard-matching/

给你一个输入字符串 (s) 和一个字符模式 (p) ，请你实现一个支持 '?' 和 '*' 匹配规则的通配符匹配：

'?' 可以匹配任何单个字符。

'*' 可以匹配任意字符序列（包括空字符序列）。

判定匹配成功的充要条件是：字符模式必须能够 完全匹配 输入字符串（而不是部分匹配）。

示例 1：
输入：s = "aa", p = "a"
输出：false
解释："a" 无法匹配 "aa" 整个字符串。
示例 2：
输入：s = "aa", p = "*"
输出：true
解释：'*' 可以匹配任意字符串。
示例 3：
输入：s = "cb", p = "?a"
输出：false
解释：'?' 可以匹配 'c', 但第二个 'a' 无法匹配 'b

class Solution {
    //主要是*可以匹配空符，1个，2个。。。。,s的[0,i],p的[0,j]
    public boolean isMatch(String s, String p) {
        if (p.equals("*")) return true;
        int m = s.length();
        int n = p.length();
        boolean[][] dp = new boolean[m + 1][n + 1];
        dp[0][0] = true;
        for (int j = 1; j <= n; j++) {
            if (p.charAt(j - 1) == '*') {
                dp[0][j] = true;
            }else 
                break;
        }

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '?') {
                    dp[i][j] = dp[i - 1][j - 1];
                } else if (p.charAt(j - 1) == '*') {
                    dp[i][j] = dp[i][j - 1] || dp[i - 1][j];//去一个空符+数学推导
                }
            }
        }
        
        return dp[m][n];
    }
}

6.两个字符串的最小ASCII删除和

712. 两个字符串的最小ASCII删除和https://leetcode.cn/problems/minimum-ascii-delete-sum-for-two-strings/

给定两个字符串s1 和 s2，返回 使两个字符串相等所需删除字符的 ASCII 值的最小和 。

示例 1:
输入: s1 = "sea", s2 = "eat"
输出: 231
解释: 在 "sea" 中删除 "s" 并将 "s" 的值(115)加入总和。
在 "eat" 中删除 "t" 并将 116 加入总和。
结束时，两个字符串相等，115 + 116 = 231 就是符合条件的最小和。
示例 2:
输入: s1 = "delete", s2 = "leet"
输出: 403
解释: 在 "delete" 中删除 "dee" 字符串变成 "let"，
将 100[d]+101[e]+101[e] 加入总和。在 "leet" 中删除 "e" 将 101[e] 加入总和。
结束时，两个字符串都等于 "let"，结果即为 100+101+101+101 = 403 。
如果改为将两个字符串转换为 "lee" 或 "eet"，我们会得到 433 或 417 的结果，比答案更大。
转化：在两个字符串中找出文章来源地址https://www.toymoban.com/news/detail-838249.html

class Solution {
    public int minimumDeleteSum(String s1, String s2) {
        int m = s1.length();
        int n = s2.length();
        int sum = 0;
        for (int i = 0; i < m; i++) {
            sum += (int) s1.charAt(i);
        }
        for (int i = 0; i < n; i++) {
            sum += (int) s2.charAt(i);
        }
        int[][] dp = new int[m + 1][n + 1];

        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] + (int) s1.charAt(i - 1);
                else
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
        return sum - 2 * dp[m][n];
    }
}

到了这里，关于两个数组的动态规划——最长公共子序列模型的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！