两个数组dp问题

最长公共子序列

题目解析：求两个字符串最长公共子序列长度
动态规划
状态表示：dp[i][j]：s1字符串[0,i]区间和s2字符串[0,j]区间所有子序列中最长公共子序列长度
状态转移方程
dp[i][j]
s1[i] == s2[j] -> dp[i-1][j-1] + 1
s1[i] != s2[j] -> max(dp[i][j-1],dp[i-1][j])
初始化
dp表多开辟一行和一列，将多开辟的初始化为0
下标对应关系有所改变
填表顺序
从上到下每一行，每一行从左到右
返回值
dp[m][n]
m = s1.length
n = s2.length

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length();
        int 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] = dp[i-1][j-1] + 1;
                }else{
                    dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);
                }
            }
        }
        return dp[m][n];
    }
}

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length();
        int n = text2.length();

        int[][] dp = new int[m+1][n+1];
        //加一个空格，与dp表下标一一对应
        text1 = " " + text1;
        text2 = " " + text2;
        for(int i = 1;i <= m;i++){
            for(int j = 1;j <= n;j++){
                if(text1.charAt(i) == text2.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];
    }
}

不相交的线

题目解析：两个数组相同的数进行连线，所有连线不可以相交，求最长连线个数
通过上面发现，这里两个数组进行连线的数，其对应的子序列是一样的，这里转化为求两个数组最长公共子序列
动态规划
状态表示：dp[i][j]：nums1数组[0,i]区间和nums2数组[0,j]区间所有子序列中最长公共子序列长度
状态转移方程
dp[i][j]
nums1[i] == nums2[j] -> dp[i-1][j-1] + 1
nums1[i] != nums2[j] -> max(dp[i][j-1],dp[i-1][j])
初始化
dp表多开辟一行和一列，将多开辟的初始化为0
下标对应关系有所改变
填表顺序
从上到下每一行，每一行从左到右
返回值
dp[m][n]
m = nums1.length
n = nums2.length

class Solution {
    public int maxUncrossedLines(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;

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

不同子序列

题目解析：求s字符串中所有子串中有多少个t字符串
动态规划
状态表示
dp[i][j]：s字符串[0,j]区间所有子序列中有多少个t字符串[0,i]子串
状态转移方程
从s[0,j]区间所有子序列中找有多少个t字符串[0,i]子串，其肯定包括从s[0,j-1]区间所有子序列中找有多少个t字符串[0,i]子串，如果此时s[j] == t[i]，加上从s[0,j-1]区间所有子序列中找有多少个t字符串[0,i-1]子串
dp[i][j] = dp[i][j-1] + dp[i-1][j-1]（s[j] == t[i]）
初始化
可以多开辟一行和一列
多的一行初始化为1，多的一列初始化为0
填表顺序
从上到下每一行
每一行从左向右
返回值
dp[m][n]

class Solution {
    public int numDistinct(String s, String t) {
        int m = t.length();
        int n = s.length();
        int[][] dp = new int[m+1][n+1];
        //第一行初始化为1，因为此时t是空串，s中肯定有空串
        for(int i = 0;i <= n;i++){
            dp[0][i] = 1;
        }
        for(int i = 1; i <= m;i++){
            for(int j = 1;j <= n;j++){
                //两种
                //不包含s[j]
                dp[i][j] = dp[i][j-1];
                //包含需要满足t[i] == t[j]
                if(t.charAt(i-1) == s.charAt(j-1)){
                    dp[i][j] += dp[i-1][j-1];
                }
            }
        }
        return dp[m][n];
    }
}

通配符匹配

题目解析：一个字符串p有 ？和 *和正常字符，？可以匹配任意一个字符，可以匹配任意个字符，p字符串是否可以完全匹配s字符串
动态规划
状态表示
dp[i][j]：p字符串[0,j]区间子串是否可以匹配s字符串中[0,i]区间子串
状态转移方程
根据p[j]位置字符进行划分
p[j] 是普通字符 s[i] == p[j] && dp[i-1][j-1]
p[j]是 ？可以匹配任意字符 dp[i-1][j-1]
p[j]是 * dp[i-1][j] || dp[i][j-1]
初始化
可以多开辟一行和一列
多的一列初始化为false，多的一行如果p对应[0,j]区间都是初始化为true，反之false
填表顺序
从上到下每一行
每一行从左向右
返回值
dp[m][n]

class Solution {
    public boolean isMatch(String _s, String _p) {
        int m = _s.length();
        int n = _p.length();
        boolean[][] dp = new boolean[m+1][n+1];
        //使下标对应关系一一对应
        _s = " " + _s;
        _p = " " + _p;
        char[] s = _s.toCharArray();
        char[] p = _p.toCharArray();
        //初始化第一行
        for(int j = 1;j <= n;j++){
            if(p[j] == '*'){
                dp[0][j] = true;
            }else{
                break;
            }
        }
        dp[0][0] = true;
        for(int i = 1;i <= m;i++){
            for(int j = 1;j <= n;j++){
                if(p[j] == '*'){
                    dp[i][j] = dp[i][j-1] || dp[i-1][j];
                }else{
                    dp[i][j] = (s[i] == p[j] || p[j] == '?') && dp[i-1][j-1];
                }
            }
        }
        return dp[m][n];
    }
}

正则表达式匹配

题目解析：一个字符串p是否可以完全匹配字符串s
p字符串中 '.'字符可以匹配任意一个字符
’ * '字符需要结合前面一个字符，可以表示0/多个前面一个字符(可以将其和前面一个字符看成整体)
动态规划
状态表示
dp[i][j]：p字符串[0,j]区间子串是否可以匹配s字符串中[0,i]区间子串
状态转移方程
根据p[j]位置字符进行划分
p[j]是 * 字符：dp[i][j-2] || (p[j-1] == s[i] || p[j-1] == ’ . ') && dp[i-1][j]
p[i]是正常字符 / . 字符：(p[j] == s[i] || p[j] == ‘;’) && dp[i-1][j-1]
初始化
可以多开辟一行和一列
多的一列初始化为false
因为此时只有 _这种情况才可以表示空，因此第一行，当p字符串中偶数个字符是是，其和前面字符都位置是true，如果一个不是，当前及其后面都是false
填表顺序
从上到下每一行
每一行从左向右
返回值
dp[m][n]

class Solution {
    public boolean isMatch(String _s, String _p) {
        int m = _s.length();
        int n = _p.length();
        _s = " " + _s;
        _p = " " + _p;
        char[] s = _s.toCharArray();
        char[] p = _p.toCharArray();
        boolean[][] dp = new boolean[m+1][n+1];

        for(int j = 2;j <= n;j+=2){
            if(p[j] == '*'){
                dp[0][j-1] = dp[0][j] = true;
            }else{
                break;
            }
        }
        dp[0][0] = true;
        for(int i = 1;i <= m;i++){
            for(int j = 1;j <= n;j++){
                if(p[j] == '*'){
                   dp[i][j] =  dp[i][j-2] ||((p[j-1] == '.' || p[j-1] == s[i]) && dp[i-1][j]);
                }else{
                    dp[i][j] = (p[j] == '.' || p[j] == s[i]) && dp[i-1][j-1];
                }
            }
        }
        return dp[m][n];
    }
}

交错字符串

题目解析：判断s3字符串是否由s1和s2交错组成，也就是由s1和s2子串组成
动态规划
状态表示
预处理：将s1和s2和s3都向后移动一位，方便操作
dp[i][j]：s1中[1,i]区间字符串和s2中[1,j]区间字符串是否可以组成s3中[1,i+j]区间字符串
状态转移方程
dp[i][j] = (s1[i] == s3[i + j] && dp[i - 1][j]) || (s2[j] == s3[i + j] && dp[i][j - 1])
初始化
可以多开辟一行和一列
第一行表示s1为空，s2和s3非空，直接判断s3是否由s2组成，每个字符一一对应
第一行表示s2为空，s1和s3非空，直接判断s3是否由s1组成，每个字符一一对应
填表顺序
从上到下每一行
每一行从左向右
返回值
dp[m][n]

class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        int m = s1.length();
        int n = s2.length();
        if (m + n != s3.length()) {
            return false;
        }
        //都后移动一位
        s1 = " " + s1;
        s2 = " " + s2;
        s3 = " " + s3;

        boolean[][] dp = new boolean[m + 1][n + 1];
        //初始化第一行
        for (int j = 1; j <= n; j++) {
            if (s2.charAt(j) == s3.charAt(j)) {
                dp[0][j] = true;
            } else {
                break;
            }
        }
        //第一列
        for (int i = 1; i <= m; i++) {
            if (s1.charAt(i) == s3.charAt(i)) {
                dp[i][0] = true;
            } else {
                break;
            }
        }
        dp[0][0] = true;
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {

                dp[i][j] = (s1.charAt(i) == s3.charAt(i+j) && dp[i - 1][j])
                        || (s2.charAt(j) == s3.charAt(i+j) && dp[i][j - 1]);

            }
        }
        return dp[m][n];
    }
}

可以使用字符数组替代字符串，这样查找效率较高

class Solution {
    public boolean isInterleave(String _s1, String _s2, String _s3) {
        int m = _s1.length();
        int n = _s2.length();
        if (m + n != _s3.length()) {
            return false;
        }
        //都后移动一位
        _s1 = " " + _s1;
        _s2 = " " + _s2;
        _s3 = " " + _s3;
        char[] s1 = _s1.toCharArray();
        char[] s2 = _s2.toCharArray();
        char[] s3 = _s3.toCharArray();

        boolean[][] dp = new boolean[m + 1][n + 1];
        //初始化第一行
        for (int j = 1; j <= n; j++) {
            if (s2[j] == s3[j]) {
                dp[0][j] = true;
            } else {
                break;
            }
        }
        //第一列
        for (int i = 1; i <= m; i++) {
            if (s1[i] == s3[i]) {
                dp[i][0] = true;
            } else {
                break;
            }
        }
        dp[0][0] = true;
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {

                dp[i][j] = (s1[i] == s3[i + j] && dp[i - 1][j]) || (s2[j] == s3[i + j] && dp[i][j - 1]);

            }
        }
        return dp[m][n];
    }
}

两个字符串的最小ASCLL删除和

题目解析：找出让s1和s2两个字符串变成相同字符串，最小删除字符ASCLL码总和
题目转化：求两个字符最大公共子序列的ASCLL码的总和
动态规划
状态表示
dp[i][j]：s1中[1,i]区间和s2中[1,j]区间所有子序列中，最大公共子序列的ASCLL码的总和
状态转移方程
if s1[ i ] == s2[ j ] dp[i][j] = max(dp[i - 1][j], dp[i][j - 1],dp[i-1][j-1] + s1[i])
反之：dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1])
填表顺序
从上到下每一行
每一行从左向右
返回值
sum - dp[m][n]- dp[m][n]

这里dp表多开辟一行和一列，因此下标对应关系有所改变
方式一：.dp[i][j]对应的是s1的[0,i-1]和s2[0,j-1]区间
方式二：可以让s1和s2向后移动，让下标对应,s1 = " " + s1 ,s2 = " " + s2(但这里求总和sum要提前算)

class Solution {
    public int minimumDeleteSum(String s1, String s2) {
        int m = s1.length();
        int n = s2.length();
        //公共子序列最大ASCLL和
        int[][] dp = new int[m + 1][n + 1];
        
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                if (s1.charAt(i-1) == s2.charAt(j-1)) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - 1] + s1.charAt(i-1));
                }
            }
        }
        int sum = 0;//s1和s2中的ASCLL和
        for(char ch : s1.toCharArray()){
            sum += ch;
        }
        for(char ch : s2.toCharArray()){
            sum += ch;
        }
        return sum - 2 * dp[m][n];
    }
}

最长重复子数组

题目解析：求两个数组nums1和nums2最长公共子数组长度
动态规划
动态规划
状态表示
dp[i][j]：nums1数组以i位置结尾和nums2数组以j位置结尾最长公共子数组长度
状态转移方程
nums1[i] == nums[j] -> dp[i-1][j-1] + 1,反之为0
填表顺序
整体从上向下
返回值
dp表中最大值

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;
    }
}

转载自 CSDN-专业IT技术社区

原文链接：https://blog.csdn.net/2401_89019969/article/details/155889975