不同的子序列 II
【摘要】 不同的子序列 II难度:困难 题目给定一个字符串 s,计算 s 的 不同非空子序列 的个数。因为结果可能很大,所以返回答案需要对 10^9 + 7 取余 。字符串的 子序列 是经由原字符串删除一些(也可能不删除)字符但不改变剩余字符相对位置的一个新字符串。例如,“ace” 是 “abcde” 的一个子序列,但 “aec” 不是。示例 1:输入:s = "abc"输出:7解释:7 个不同的子序...
不同的子序列 II
难度:困难
题目
给定一个字符串 s,计算 s 的 不同非空子序列 的个数。因为结果可能很大,所以返回答案需要对 10^9 + 7 取余 。
字符串的 子序列 是经由原字符串删除一些(也可能不删除)字符但不改变剩余字符相对位置的一个新字符串。
例如,“ace” 是 “abcde” 的一个子序列,但 “aec” 不是。
示例 1:
输入:s = "abc"
输出:7
解释:7 个不同的子序列分别是 "a", "b", "c", "ab", "ac", "bc", 以及 "abc"。
示例 2:
输入:s = "aba"
输出:6
解释:6 个不同的子序列分别是 "a", "b", "ab", "ba", "aa" 以及 "aba"。
示例 3:
输入:s = "aaa"
输出:3
解释:3 个不同的子序列分别是 "a", "aa" 以及 "aaa"。
提示:
1 <= s.length <= 2000
s 仅由小写英文字母组成
题解
子序列的定义:从原序列中任意选择一些项,保持相对序列不变,得到的就是原序列的子序列
方程状态定义,dp[i]就为到索引为i的文字为止,能生成的子序列的个数
例如:初始状态dp[0] = dp[-1] * 2 + 1; // 非法的值赋为0,所以dp[0] 为1
状态方程推断
如果当前的文字没有出现过,那么当前位置能新生成子序列的个数就为,前一位的个数 + 自己,总数就为 前一位的个数 + 前一位的个数 + 1
dp[I] = dp[i-1] * 2 - 1;
如果当前的文字出现过,自己就不能加进去了,新生成的就为 前一位的个数 + 前一位的个数 - 重复的个数
此时重复的个数是多少呢,是这个文字前一次的位置的【除了自己以外的新生成】,假设这个文字当前的位置是i,上一次位置是j,那么重复的个数为dp[j - 1]
/**
* @param {string} S
* @return {number}
*/
var distinctSubseqII = function (S) {
const dp = [];
const count = {};
const MOD = 1000000007;
let length = S.length;
for (let i = 0; i < length; i++) {
const preDp = dp[i - 1] || 0;
if (typeof count[S[i]] === 'undefined') {
dp[i] = preDp * 2 + 1;
} else {
const prePositionDp = dp[count[S[i]] - 1] || 0;
dp[i] = preDp * 2 - prePositionDp;
if (dp[i] < 0) {
dp[i] += MOD;
}
}
dp[i] %= MOD;
count[S[i]] = i;
}
return dp[S.length - 1];
};
总结
动态规划是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的,通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。 动态规划常常适用于有重叠子问题和最优子结构性质的问题,动态规划方法所耗时间往往远少于朴素解法。 动态规划背后的基本思想非常简单。
【声明】本内容来自华为云开发者社区博主,不代表华为云及华为云开发者社区的观点和立场。转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息,否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱:
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
作者其他文章
评论(0)