动态规划-两个数组的dp问题2

时间：2024-05-07 18:05:40

文章目录

  • 1. 不同的子序列（115）
  • 2. 通配符匹配（44）

1. 不同的子序列（115）

题目描述：
在这里插入图片描述

状态表示：
根据题意这里的dp数组可以定义为二维，并且dp[i][j]表示字符串t的0到i的区间的子串在字符串s的0到j区间的子串的子序列中出现的次数也就是匹配次数。
状态转移方程：
将这里的状态分为两种情况，第一种情况就是当s的0到j这个区间的子序列不以j位置元素为结尾，那么dp[i][j]可以表示为dp[i][j]=dp[i][j-1],因为在这种情况下s的子序列不以j位置为结尾，那么直接将字符串r的指定区间内的子串和s的0到j-1区间的子序列进行匹配即可。第二种情况就是s字符串的0到j的区间内的子序列以j位置元素为结尾，那么当j位置元素与i位置元素相等时就可以得到dp[i][j]=dp[i][j]，因为在此时t的子串最后一位元素已经和s的0到j区间的子序列最后一位元素相等了，那么直接去考虑前面的情况，正好前面的情况可以直接表示。在这种状态分类下，两者的结果要相加，具体看代码。
初始化：
初始化为了防止越界，给dp这个二维数组加上一行一列。然后这一行一列从逻辑上很好给他们赋值，因为加上dp的是第0行和第0列，所以逻辑上可以将其理解为s和t分别为空串的情况，当t为空串时，s中可以和其匹配只有一种可能那就是也是空串，所以第0行都赋为1。当s为空串时，其中肯定没有跟t匹配的子序列了，因此第一列直接全赋为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];

        for (int i = 0; i <= n; i++) {
            dp[0][i] = 1;
        }

        t = " " + t;
        s = " " + s;

        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) == s.charAt(j)) {
                    dp[i][j] += dp[i - 1][j - 1];
                }

            }
        }

        return dp[m][n];

    }
}

题目链接
时间复杂度:O(N^2)
空间复杂度:O(N^2)

2. 通配符匹配（44）

题目描述：
在这里插入图片描述

状态表示：
使用二维数组dp，使用dp[i][j]表示s在区间0-i上的子串能否和p在0-j上的子串相匹配。
状态转移方程：
对于这种两个数组的dp问题，都会对两个子串的最后一个元素进行考虑，因此这里的状态转移可以分为三种情况。第一种情况当模式串p的子串最后一个元素是一个普通的字符时，那么当s[i]==p[j]时，dp[i][j]=dp[i-1][j-1]。第二种情况当模式串的子串最后一个元素是?时，?可以匹配任何一个单个字符，所以此时的状态转移方程为dp[i][j]=dp[i-1][j-1]。第三种情况时模式串p的子串最后一个元素为*时，因为可以匹配任意个子符，所以理论上这里有很多种情况，当不匹配字符时，dp[i][j]=dp[i][j-1]，当匹配一个字符时，dp[i][j]=dp[i-1][j-1]，当匹配两个字符时dp[i][j]=dp[i-2][j-1]等等。
事实上第三种情况可以使用循环处理，但是效率不高，因此这里使用数学的方法对第三种情况进行优化。通过上面的分析我们知道在第三种情况下dp[i][j]=dp[i][j-1] || dp[i-1][j-1] || dp[i-2][j-1]…那么这里我们再分析dp[i-1][j]的一个状态转移方程，再第三种情况下，不难发现dp[i-1][j]=dp[i-1][j-1] || dp[i-2][j-1] || dp[i-3][j-1]…通过这两个式子的相似之处我们就可以得到dp[i][j]=dp[i][j-1] || dp[i-1][j]。

初始化：
为了避免数组越界也就是方便我们进行运算，给dp二维数组加上一行和一列，对于第一行在逻辑上的意味就是对于s子串是空串的情况下是否能够和模式串p进行匹配，模式串p的子串是空串只有在它的字符全部是*的情况下才可以成立，因此第一行我们使用一个循环来进行处理。对于第一列意味着p的子串为空串的情况，此时当然是无法匹配的，全部赋为false即可。第一行和第一列的交界处比较特殊，此时p的子串和s的子串都是空串，因此是匹配的，所以dp[0][0]赋为true。

填表顺序：
从上到下，从左至右。
返回值：
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];
        dp[0][0] = true;

        s = " " + s;
        p = " " + p;

        for (int i = 1; i <= n; i++) {
            if (p.charAt(i) == '*') {
                dp[0][i] = true;
            } else {
                break;
            }
        }

        for (int i = 1; i <= m; i++) {

            for (int j = 1; j <= n; j++) {
                if (p.charAt(j) == '?') {
                    dp[i][j] = dp[i - 1][j - 1];
                } else if (p.charAt(j) == '*') {

                    if (dp[i][j - 1] || dp[i - 1][j]) {
                        dp[i][j] = true;
                    }

                } else {
                    if (s.charAt(i) == p.charAt(j)) {
                        dp[i][j] = dp[i - 1][j - 1];
                    }
                }

            }

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

题目链接
时间复杂度:O(N^2)
空间复杂度:O(N^2)

相关文章