（熬夜肝）动态规划-不同的子序列-一一网

这是我参与更文挑战的第23天，活动详情查看：更文挑战

$\color{red}{如果你对动态规划不熟悉，望转到该篇~}$

肝了好多天-动态规划十连-超细腻解析｜刷题打卡

$\color{green}{这道题很有意思，不看后悔！? ? ? ~}$

什么题可以选择动态规划来做？

1.计数

有多少种方式走到右下角
有多少种方法选出k个数是的和是sum

2.求最大值最小值

从左上角走到右下角路径的最大数字和
最长上升子序列长度

3.求存在性

取石子游戏,先手是否必胜
能不能选出k个数使得和是sum

leecode 115. 不同的子序列

给定一个字符串 s 和一个字符串 t ，计算在 s 的子序列中 t 出现的个数。

字符串的一个子序列是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。

（例如，”ACE” 是 “ABCDE” 的一个子序列，而 “AEC” 不是）

题目数据保证答案符合 32 位带符号整数范围。

示例 1：

输入：s = “rabbbit”, t = “rabbit”

输出：3

解释：
如下图所示, 有 3 种可以从 s 中得到 “rabbit” 的方案。

(上箭头符号 ^ 表示选取的字母)

rabbbit

^^^^ ^^

rabbbit

^^ ^^^^

rabbbit

^^^ ^^^

示例 2：

输入：s = “babgbag”, t = “bag”

输出：5

解释：
如下图所示, 有 5 种可以从 s 中得到 “bag” 的方案。
(上箭头符号 ^ 表示选取的字母)

babgbag

^^ ^

babgbag

^^ ^

babgbag

^ ^^

babgbag

^ ^^

babgbag

    ^^^
复制代码

提示：

0 <= s.length, t.length <= 1000
s 和 t 由英文字母组成

—

动态规划四步走~~~ ❤️❤️❤️❤️

2.1. 动态规划组成部分1：确定状态

简单的说，解动态规划的时候需要开一个数组，数组的每个元素f[i]或者f[i][j]代表什么，类似数学题中x, y, z代表什么

最后一步

如果说s字符串是t字符串的子序列，我们直接比较最后一个字母是否相等（因为s和t都只有一个字母时，它们就是最后一个字母）

例如： s = “babgbag”, t = “bag”

这里s字符串的长度如果小于t字符串的长度，直接返回0, 没有子序列。

子问题

子问题分析，我们判断最后一个字母是否匹配，那么就有两种情况

–如果最后一个字母匹配：

可以推导出：dp[i][j]=dp[i+1][j+1]+dp[i+1][j], 看j+1是否是i+1的子序列, 这里加上dp[i+1][j]是因为，例如：s =babc , t=bc ,当s字符串的第二个b去匹配t字符串的第一个b字符时，需要加上之前不匹配的子序列。

–如果最后一个字母不匹配：

可以推导出： dp[i][j]=dp[i+1][j] 看j是否是i+1的子序列，就比如：s = bac ,t = bc

$\color{yellow}{很nice ~}$ ❤️❤️❤️

2.2. 动态规划组成部分2：转移方程

看了子问题分析，其实就是这两种情况的分析。

转移方程就很好写了：

dp[i][j]=dp[i+1][j+1]+dp[i+1][j]

dp[i][j]=dp[i+1][j]

2.3. 动态规划组成部分3：初始条件和边界情况

s的字符串长度>= t的字符串长度

如果t的字符串为空，那么空是可以作为s的子序列的。

2.4. 动态规划组成部分4：计算顺序

自顶向下或者自底向上

参考代码

GO语言版

func numDistinct(s, t string) int {
        m, n := len(s), len(t)
        if m < n {
            return 0
        }
        dp := make([][]int, m+1)
        for i := range dp {
            dp[i] = make([]int, n+1)
            dp[i][n] = 1   // // 对t来说，如果t为空，空是s字符串的子序列，所以空是s的每个字符的子序列组
        }
        for i := m - 1; i >= 0; i-- {
            for j := n - 1; j >= 0; j-- {
                if s[i] == t[j] {
                    dp[i][j] = dp[i+1][j+1] + dp[i+1][j]
                } else {
                    dp[i][j] = dp[i+1][j]
                }
            }
        }
        return dp[0][0]
    }



复制代码

JAVA版

 
    public int numDistinct(String s, String t) {
        int m = s.length(), n = t.length();
        if (m < n) {
            return 0;
        }
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 0; i <= m; i++) {
            dp[i][n] = 1; // 对t来说，如果t为空，空是s字符串的子序列，所以空是s的每个字符的子序列组合。
        }
        for (int i = m - 1; i >= 0; i--) {
            char sChar = s.charAt(i);
            for (int j = n - 1; j >= 0; j--) {
                char tChar = t.charAt(j);
                if (sChar == tChar) {
                    dp[i][j] = dp[i + 1][j + 1] + dp[i + 1][j];
                } else {
                    dp[i][j] = dp[i + 1][j];
                }
            }
        }
        return dp[0][0];
    }

    @Test
    public void isnumDistinct() {
        int i = numDistinct("babc","bc");
        Assert.assertNotNull(i);
    }


    

复制代码