不同的子序列 II

2022-10-14
中国台湾
本文字数：1028 字
阅读完需：约 3 分钟

难度：困难

题目

给定一个字符串 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];};

复制代码

总结

动态规划是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划常常适用于有重叠子问题和最优子结构性质的问题，动态规划方法所耗时间往往远少于朴素解法。动态规划背后的基本思想非常简单。

发布于: 刚刚阅读数: 4

原文链接:【http://xie.infoq.cn/article/5284dbd09088e52ccc0114992】。文章转载请联系作者。

掘金安东尼

关注

安东尼陪你度过漫长编程岁月~ 2022-07-14 加入

真正的大师，永远怀着一颗学徒的心（易）

发布

暂无评论

创作场景

不同的子序列 II

题目

题解

总结

掘金安东尼

评论