题意理解:
给你两个字符串 s
和 t
,统计并返回在 s
的 子序列 中 t
出现的个数,结果需要对 109 + 7 取模。
即此题可以理解为:从s中删除元素去构造t,有多少种方法
或者也可以理解为:s中按顺序取t,有多少个
则一定有s和t的最长公共子序列为t, 那么s中有多少个这样的最长公共子序列呢。
这里采用动态规划思路来解题,则首先要明确dp数组的含义。
解题思路:
(1)定义dp数组
dp[i][j]表示s的第i个元素前有多少个t的第j个元素前子串。
(2)初始化
dp[i][0]表示s的第i个元素前有多少个空串,dp[i][0]=1
dp[0][j]表示空串里有多少个t的字串,dp[0][j]=0
特别的dp[0][0]=1
(3)递推公式
当且仅当: s[i-1]==t[j-1]时
此时有两种情况:
dp[i][j]=使用这个可以匹配的字符+不适用这个可以匹配的,尝试下一个可以匹配的字符
=dp[i-1][j-1](使用是s[i-1])+dp[i-1][j](不使用s[i-1],继续下一字符匹配)
否则: dp[i][j]=(不是使用该字符匹配)dp[i][j-1]
(4)遍历顺序:总是从上到下,从左到右
(5)返回
dp[s.size][t.size]