From
Leetcode
Status
回头复习下
Date
Apr 25, 2024
Tags
动态规划
背包问题
子序列问题
Difficulty
困难
题面
给你两个字符串
s 和 t ，统计并返回在 s 的 子序列 中 t 出现的个数，结果需要对 109 + 7 取模。示例 1：
示例 2：
提示：
1 <= s.length, t.length <= 1000
s和t由英文字母组成
思路
另一种动态规划的方法，其实这道题是一个标准的01背包问题，可以转化成这样：
现在有7个物品“babgbag", 依次放进size为3的背包"bag"中，但放进背包的条件是只有字符相等才能放，可以选择放与不放
和背包问题一样，定义dp_i,j为前0~i个物品放入容量为j的背包的方法，递推公式是
dp_i,j = dp_i-1,j + (if s_i == t_j) dp_i-1,j-1
另一种理解：
dp[i][j]：以i-1为结尾的s子序列中出现以j-1为结尾的t的个数为dp[i][j]。
这一类问题，基本是要分析两种情况
- s[i - 1] 与 t[j - 1]相等
- s[i - 1] 与 t[j - 1] 不相等
当s[i - 1] 与 t[j - 1]相等时，dp[i][j]可以有两部分组成。
一部分是用s[i - 1]来匹配，那么个数为dp[i - 1][j - 1]。即不需要考虑当前s子串和t子串的最后一位字母，所以只需要 dp[i-1][j-1]。
一部分是不用s[i - 1]来匹配，个数为dp[i - 1][j]。