怎么做网站 教学,广州seo顾问服务,logo在线查询,宁波最好的推广平台今日份题目#xff1a;
给你两个字符串 s 和 t #xff0c;统计并返回在 s 的 子序列 中 t 出现的个数。
题目数据保证答案符合 32 位带符号整数范围。
示例1
输入#xff1a;s rabbbit, t rabbit
输出#xff1a;3
解释#xff1a;
如下所…今日份题目
给你两个字符串 s 和 t 统计并返回在 s 的 子序列 中 t 出现的个数。
题目数据保证答案符合 32 位带符号整数范围。
示例1
输入s rabbbit, t rabbit
输出3
解释
如下所示, 有 3 种可以从 s 中得到 rabbit 的方案。
rabbbit选前两个b
rabbbit选后两个b
rabbbit选两头的b
示例2
输入s babgbag, t bag
输出5
提示 1 s.length, t.length 1000 s 和 t 由英文字母组成
题目思路
这道题目的思路和之前的子序列的思路不太一样的地方在于这道题用到的是当前位置到字符串最后位置的子问题而之前的题是当前位置到开头位置的子问题。
状态转移方程
当 s[i]t[j] 时dp [ i ] [ j ]由两部分组成
如果 s[i]和 t[j]匹配则考虑 t[j1:] 作为 s[i1:]的子序列子序列数为 dp [ i1 ] [ j1 ]
如果 s[i] 不和 t[j] 匹配则考虑 t[j:] 作为 s[i1:]的子序列子序列数为 dp [ i1 ] [ j ]。
因此当 s[i]t[j] 时有 dp [ i ] [ j ] dp [ i1 ] [ j1 ]dp[ i1 ] [ j ]。
当 s[i]≠t[j] 时s[i]不能和 t[j]匹配因此只考虑 t[j:]作为 s[i1:] 的子序列子序列数为 dp[i1] [j]。
因此当 s[i]≠t[j] 时有 dp [ i ] [ j ]dp [ i1 ] [ j ]。
得状态转移总方程 这道题目好难我也是有点晕如果大家有疑问欢迎评论区讨论哦
代码
class Solution
{
public:int numDistinct(string s, string t) {//获取两个字符串的长度int n s.length();int m t.length();if (nm) return 0;unsigned long long dp[2000][2000]{0};//初始化边界数值for(int i0;in;i)//此时t[m-末尾]为空字符串故对于任何字符串空字符串都是其子序列为1 {dp[i][m]1;}//更新所有dp值for(int in-1;i0;i--) {char scs[i];for(int jm-1;j0;j--) {char tct[j];if(sctc) {dp[i][j]dp[i1][j1]dp[i1][j];} else {dp[i][j]dp[i1][j];}}}return dp[0][0];}
};提交结果 欢迎大家在评论区讨论如有不懂的代码部分欢迎在评论区留言
