不同的子序列

[编程题]不同的子序列

热度指数：19635 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

给定两个字符串S和T，返回S子序列等于T的不同子序列个数有多少个？

字符串的子序列是由原来的字符串删除一些字符（也可以不删除）在不改变相对位置的情况下的剩余字符（例如，"ACE"is a subsequence of"ABCDE"但是"AEC"不是）
例如：

S="nowcccoder", T = "nowccoder"

返回3

示例1

输入

"nowcccoder","nowccoder"

输出

算法知识视频讲解

华科不平凡

发表于 2020-08-25 10:27:57

“求子序列个数”，毋庸置疑，这是一道动态规划题。首先定义dp[i][j]的含义：S[0..j-1]中包含T[0..i-1]的子序列个数，接下来定义状态公式：状况1: dp[i][j]=dp[i][j-1]（如果T[i-1]!=S[j-1]）状况2：dp[i][j]=dp[i][j-1] + d 展开全文

牛客141762904号

发表于 2020-03-24 23:43:05

用了一个下午，，，，和晚上，vegetable 思路：目标的抽取，即问题的解构或者拆解方式：用dp，将问题抽取为在每个母串的各个长度区间上（0-n），各个长度的子串（0-m）在这个区间上匹配的数目。用一个二维表格，行是字串的各个字母，列是母串的各个字母。每个元素的行i代表此次迭代所用字串为0-i的展开全文

ls.joshua

发表于 2020-04-21 11:38:44

状态转移方程：dp[i][j] = sum(dp[i-1][0],...,dp[i-1][j-1]);还可以继续优化，可以用空间换时间，减少求解dp[i][j]的查询数量，贴出代码，请大佬给出更优的算法，以此共勉！ class Solution { public: int numDistin 展开全文