文章目錄

• • 1. 題目
  • 2. 解題

1. 題目

給定一個字符串 S，計算 S 的不同非空子序列的個數。

因為結果可能很大，所以返回答案模 10^9 + 7.

示例 1： 輸入："abc" 輸出：7 解釋：7 個不同的子序列分別是 "a", "b", "c", "ab", "ac", "bc", 以及 "abc"。示例 2： 輸入："aba" 輸出：6 解釋：6 個不同的子序列分別是 "a", "b", "ab", "ba", "aa" 以及 "aba"。示例 3： 輸入："aaa" 輸出：3 解釋：3 個不同的子序列分別是 "a", "aa" 以及 "aaa"。提示： S 只包含小寫字母。 1 <= S.length <= 2000

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/distinct-subsequences-ii
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

2. 解題

class Solution { public:int distinctSubseqII(string S) {int n = S.size(), mod = 1e9+7;vector<int> dp(n+1, 0);dp[0] = 1;//空字符串vector<int> prev(26, -1);// 之前最近的相同字符 posfor(int i = 0; i < n; i++) {dp[i+1] = (dp[i]*2)%mod;// 當前字符跟之前的結合，不結合，產生的方案數if(prev[S[i]-'a'] != -1)// 之前有重復的 相同字符，會產生重復計數dp[i+1] = (dp[i+1]-dp[prev[S[i]-'a']]+mod)%mod;prev[S[i]-'a'] = i;//更新最近的字符位置}return dp[n]-1;} };

0 ms 7.1 MB C++

---

我的CSDN博客地址 https://michael.blog.csdn.net/

長按或掃碼關注我的公眾號（Michael阿明），一起加油、一起學習進步！

總結

以上是生活随笔為你收集整理的LeetCode 940. 不同的子序列 II（动态规划）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。