力扣115-不同的子序列（Java详细题解）

这篇文章介绍了力扣115-不同的子序列（Java详细题解），分享给大家做个参考，收藏Python资料网收获更多编程知识

题目链接：不同的子序列

前情提要：

因为本人最近都来刷dp类的题目所以该题就默认用dp方法来做。

dp五部曲。

1.确定dp数组和i下标的含义。

2.确定递推公式。

3.dp初始化。

4.确定dp的遍历顺序。

5.如果没有ac打印dp数组 利于debug。

每一个dp题目如果都用这五步分析清楚，那么这道题就能解出来了。

题目思路:

本题的题目描述非常清晰，返回t字符串在s字符串中出现的个数。该题与力扣392类似，力扣392中是判断t能不能在s中出现，而本题是要求t在s中出现的个数。

话不多说，直接开始我们的dp五部曲。

1.确定dp数组和i下标的含义。

因为要需要比较俩个字符串的元素，所以我们需要用一个二维dp数组来记录每一个元素比较的结果。

dp[i] [j]指的就是以i - 1为结尾的s中有以j - 1为结尾的t的个数（在s中删除元素得到t的方法数）。

至于为什么要定义i - 1，j - 1可以看看这篇力扣718-最长重复子数组（Java详细题解）-CSDN博客。

2.确定递推公式。

子序列问题都要考虑nums[i - 1] 是否等于 nums[j - 1]的情况。

• 相等的情况。

  其实相等的情况还要分俩种。

  • 第一种 考虑用nums[i - 1]匹配nums[j - 1]。即s不删除元素得到t的方法数。

    此时dp[i] [j] = dp[i - 1] [j - 1]。因为用i - 1结尾的元素与j - 1结尾的元素匹配，而他们末尾的元素是相同的，所以s出现t的个数就由以元素前一位为结尾的dp数组决定。

  • 第二种 不考虑用nums[i - 1]匹配nums[j - 1]。即s删除元素得到t的方法数。

    此时dp[i] [j] = dp[i - 1] [j]。因为我们不用i - 1结尾的元素与j - 1结尾的元素匹配，所以我们就找i - 1前一个的元素与j - 1匹配 （即删除nums[i - 1]这个元素）。

    这里可能有人不明白了，为什么还要考虑 不用s[i - 1]来匹配，都相同了指定要匹配啊。

    例如： s：bagg 和 t：bag ，s[3] 和 t[2]是相同的，但是字符串s也可以不用s[3]来匹配，即用s[0]s[1]s[2]组成的bag。

    当然也可以用s[3]来匹配，即：s[0]s[1]s[3]组成的bag。

    dp[i - 1] [j]的含义就是以i - 2为结尾的s中出现以j - 1为结尾的t的个数。

    总之不相等的情况递推公式为：dp[i] [j] = dp[i - 1] [j - 1] + dp[i - 1] [j]；

• 不相等的情况

  既然结尾的元素都不相等了，那我们肯定是要删除s中最后一位元素，所以dp[i] [j] = dp[i - 1] [j]；

3.dp初始化。

由递推公式可知dp[i] [j]都是由dp[i - 1] [j - 1]和dp[i - 1] [j]推来的，所以在二维dp数组中就是由它的左上方和左方推来的。

所以第一列和第一排是递推的起点。

因为dp[i] [0]（第一列）是指以i - 1为结尾的s中出现空串的个数。（以i - 1为结尾的s中删除元素得到t的方法数）

所以出现空串的删除元素方法只有一种，那就是全删了。

所以初始化的代码为：

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

dp[0] [i]是指空串中出现以i - 1为结尾的t的个数，毫无疑问肯定为0。

4.确定dp的遍历顺序。

由递推公式可知dp[i] [j]都是由dp[i - 1] [j - 1]和dp[i - 1] [j]推来的。

所以遍历顺序一定是从上到下 从左到右。

5.如果没有ac打印dp数组 利于debug。

最终代码：

class Solution {
    public int numDistinct(String s, String t) {
        //定义dp数组 以i- 1为结尾的s中有以j - 1为结尾的t的个数(在s中删除元素得到t的方法数)
        int [][] dp = new int [s.length() + 1][t.length() + 1];
        //dp初始化
        for(int i = 0;i <= s.length();i ++){
            dp[i][0] = 1;
        }
        //dp的遍历顺序
        for(int i = 1;i <= s.length();i ++){
            for(int j = 1;j <= t.length();j ++){
                //dp的递推公式
                if(s.charAt(i - 1) == t.charAt(j - 1)){
                    dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
                }else{
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return dp[s.length()][t.length()];
    }
}

这一篇博客就到这了，如果你有什么疑问和想法可以打在评论区，或者私信我。

我很乐意为你解答。那么我们下篇再见！

版权声明：本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系邮箱：jacktools123@163.com进行投诉反馈，一经查实，立即删除！