我要评论题目链接：https://leetcode.cn/problems/21dk04/description/
一、题目描述（困难）
给定一个字符串 s 和一个字符串 t ，计算在 s 的子序列中 t 出现的个数。
字符串的一个 子序列 是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。（例如，"ace" 是 "abcde" 的一个子序列，而 "aec" 不是）
题目数据保证答案符合 32 位带符号整数范围。
示例 1：
输入：s = "rabbbit", t = "rabbit"输出：3解释： 如下图所示, 有 3 种可以从 s 中得到"rabbit" 的方案。rabbbitrabbbitrabbbit
示例 2：
输入：s = "babgbag", t = "bag"输出：5解释： 如下图所示, 有 5 种可以从 s 中得到"bag" 的方案。babgbagbabgbagbabgbagbabgbagbabgbag
提示：
0 <= s.length, t.length <= 1000s和t由英文字母组成
二、分析历程
因为我就是找的动态规划的题目，所以我一开始就想着去状态转移，我就直接想着构造dp数组。但是像我这样的小白往往不知道每个dp元素到底应该是什么含义，更别提怎么推导状态转移方程式了。前期我就一直向无头苍蝇一样瞎凑，这样运气好碰对了就还好，要是碰不对就一直空耗，白白浪费大量的时间，实际上往往题目意思都还没有很透彻。
后面我学乖了，可以先暴力求解，这个过程中可以发现痛点，实际考试中我们可能并不知道能不能用动态规划，但是暴力方法也能够通过部分测试用例，我们就可以先暴力等后面有时间再用动态规划，这样我们对题目有了更清楚的了解之后再动态规划思路也更清晰。
本题的意思就是在s中不改变相对顺序，截取的子序列和t相等。很明显就可以用回溯法暴力求解。
看我的回溯代码：
class solution:
def numdistinct(self, s: str, t: str) -> int:
ans=[0]
n=len(t)
m=len(s)
def d(c,i):
for j in range(i,m):
if t[c]==s[j]:
if c==n-1:
ans[0]+=1
else:
d(c+1,j+1)
d(0,0)
return ans[0]这里d(c,i)的c表示的是匹配到t中的第c个位置，i表示s中的第i个字母。一旦某个位置匹配不成功就剪枝，不用继续递归。虽然进行了剪枝，但是很遗憾，还是超时了。
接下来进行动态规划分析，实际上t中的每个字母都要用到，而s中是选一部分符合条件的进行匹配。例如
s ="rabbbit"
t ="rabbit"
假设dp[i][j]表示s[0~j]中含有t[0~i]的情况数，因为t的每个元素都一定要用到，我就将t置于外层循环，内层遍历s。
在分析dp[i][j]之前，我们可以先认为dp[i][j]之前的都已经选择好了。那么对于dp[i][j]，无论s[j]和是t[i]是什么关系，无论遍历到是s[j]后匹配的情况数会不会增加，dp[i][j]的情况数都至少等于dp[i][j-1]。因为在遍历到s[j-1]的时候就已经有dp[i][j]种情况了，所以可以先保存dp[i][j-1]的值，也就是先将dp[i][j]=dp[i][j-1]。
另外，什么时候dp[i][j]的情况会大于dp[i][j-1]呢？其实就是当s[j]==t[i]的时候，可以增加s[0~j-1]中含有t[0~i-1]的情况数，也就是说dp[i][j]可以再加上dp[i-1][j-1]。
基本的递推关系搞清楚了，但是现在还有一个问题，就是i-1和j-1可能会溢出，还有怎么初始化？我是这样解决的：dp[0]这一行先正确赋值，然后因为dp[i][j]有值的前提是j>=i,而i又是从1开始的，所以直接令j从i开始加就可以了，这样j-1一定大于0。
三、举例推导
| r | a | b | b | b | i | t | ||
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | ||
| r | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| a | 1 | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
| b | 2 | 0 | 0 | 1 | 2 | 3 | 3 | 3 |
| b | 3 | 0 | 0 | 0 | 1 | 3 | 3 | 3 |
| i | 4 | 0 | 0 | 0 | 0 | 0 | 3 | 3 |
| t | 5 | 0 | 0 | 0 | 0 | 0 | 0 | 3 |
最后答案是3
四、动态规划代码
class solution:
def numdistinct(self, s: str, t: str) -> int:
m=len(s)
n=len(t)
dp=[[0]*m for i in range(n)]#构造dp dp[i][j]代表s[0~j]匹配到t[0~i]的情况数
l=0
#初始化dp[0]这一层
for j in range(m):
if s[j]==t[0]:
l+=1
dp[0][j]=l
#外层循环t，内层循环s,j从i开始加
for i in range(1,n):
for j in range(i,m):
dp[i][j]=dp[i][j-1]
if s[j]==t[i]:
dp[i][j]+=dp[i-1][j-1]
return dp[-1][-1]
五、结果
六、优化
空间可以优化
class solution:
def numdistinct(self, s: str, t: str) -> int:
m=len(s)
n=len(t)
if m<n:
return 0
dp=[0]*m#二维dp压缩为一维dp
l=0
for j in range(m):
if s[j]==t[0]:
l+=1
dp[j]=l
for i in range(1,n):
f=0
la=dp[i-1]
for j in range(i,m):
a=dp[j]
if f==0:
dp[j-1]=0
dp[j]=dp[j-1]
if s[j]==t[i]:
dp[j]+=la
f=1
la=a
return dp[-1]
七、总结
动态规划的题目在于精而不在多，先暴力了解题目，再一步一步打表，推演，最后优化。
-----------------------------------------------------------------------------------
csdn第四篇，希望能够对您有帮助~
发表评论