不同的子序列 II_安东尼漫长的技术岁月的技术博客_51CTO博客
source link: https://blog.51cto.com/u_13961087/5755003
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
不同的子序列 II
精选 原创
难度：困难
给定一个字符串 s，计算 s 的 不同非空子序列 的个数。因为结果可能很大，所以返回答案需要对 10^9 + 7 取余 。
字符串的 子序列 是经由原字符串删除一些（也可能不删除）字符但不改变剩余字符相对位置的一个新字符串。
例如，"ace" 是 "abcde" 的一个子序列，但 "aec" 不是。
输入：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];
};
动态规划是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。 动态规划常常适用于有重叠子问题和最优子结构性质的问题，动态规划方法所耗时间往往远少于朴素解法。 动态规划背后的基本思想非常简单。
Recommend
-
4
前端必学——函数式编程（二） 原创 掘金安东尼 2022-05-30 13:56:53
-
4
浅聊缓存函数 原创 掘金安东尼 2022-06-06 09:06:01...
-
2
浅聊组合函数 原创 掘金安东尼 2022-06-05 13:30:30...
-
2
JS 变量、作用域与内存 推荐 原创 掘金安东尼 2022-06-13 09:14:45
-
2
JS 中的集合引用类型 原创 avaScript 高级程序设计第 4 版（后简称高程4），相较于第 3 版，增加了 ES6 至 ES10 的全新内容，删除了旧...
-
4
日拱算法：多数元素 原创 突一突
-
2
简化理解：策略设计模式 推荐 原创 掘金安东尼 2022-08-09 11:12:50
-
2
两数之和难度：简单给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。你...
-
5
最大为 N 的数字组合 精选 原创 掘金安东尼 2022-10-18 09:03:19...
-
4
和至少为 K 的最短子数组 精选 原创 掘金安东尼 2022-10-26 14:24:04...
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK