940. 不同的子序列 II : 正常序列 DP 運用以及優化

題目描述

這是 LeetCode 上的 ​​940. 不同的子序列 II​​ ，難度為 困難。

Tag : 「序列 DP」、「動态規劃」

給定一個字元串 ​

​s​

​​，計算 ​

​s​

​​ 的 不同非空子序列 的個數。因為結果可能很大，是以傳回答案需要對

字元串的 子序列 是經由原字元串删除一些（也可能不删除）字元但不改變剩餘字元相對位置的一個新字元串。

例如，​

​"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"。      

提示：

• ​

  ​s​

  ​ 僅由小寫英文字母組成

序列 DP

為了友善，我們令 ​

​s​

​​ 下标從 開始，定義 為考慮前 個字元，且結尾字元為 的不同子序列的個數，其中 的範圍為 代指小寫字元 ​​

​a-z​

​。

我們有顯而易見的初始化條件 ，最終答案為 。

不失一般性考慮 該如何轉移，根據 是否為

• : 由于狀态定義限定了結尾字元必須是，因而

• : 此時可作為結尾元素，同時由于我們統計的是「不同」的子序列個數，因而「以結尾的子序列方案數」與「以結尾的子序列方案數」完全等價。

  對于以作為子序列結尾字元的方案數，容易想到其方案數等于「單獨作為子序列」+「

Java 代碼：

class Solution {
    int MOD = (int)1e9+7;
    public int distinctSubseqII(String s) {
        int n = s.length(), ans = 0;
        int[][] f = new int[n + 1][26];
        for (int i = 1; i <= n; i++) {
            int c = s.charAt(i - 1) - 'a';
            for (int j = 0; j < 26; j++) {
                if (c != j) {
                    f[i][j] = f[i - 1][j];
                } else {
                    int cur = 1;
                    for (int k = 0; k < 26; k++) cur = (cur + f[i - 1][k]) % MOD;
                    f[i][j] = cur;
                }
            }
        }
        for (int i = 0; i < 26; i++) ans = (ans + f[n][i]) % MOD;
        return      

TypeScript 代碼：

function distinctSubseqII(s: string): number {
    const MOD = 1e9+7
    let n = s.length, ans = 0
    const f = new Array<Array<number>>(n + 1)
    for (let i = 0; i <= n; i++) f[i] = new Array<number>(26).fill(0)
    for (let i = 1; i <= n; i++) {
        const c = s.charCodeAt(i - 1) - 'a'.charCodeAt(0)
        for (let j = 0; j < 26; j++) {
            if (c != j) {
                f[i][j] = f[i - 1][j]
            } else {
                let cur = 1
                for (let k = 0; k < 26; k++) cur = (cur + f[i - 1][k]) % MOD
                f[i][j] = cur
            }
        }
    }
    for (let i = 0; i < 26; i++) ans = (ans + f[n][i]) % MOD
    return      

Python 代碼：

class Solution:
    def distinctSubseqII(self, s: str) -> int:
        n, MOD = len(s), 1e9+7
        f = [[0] * 26 for _ in range(n + 1)]
        for i in range(1, n + 1):
            c = ord(s[i - 1]) - ord('a')
            for j in range(26):
                f[i][j] = f[i - 1][j] if c != j else (1 + sum(f[i - 1])) % MOD
        return int(sum(f[n]) % MOD)      

• 時間複雜度：，其中
• 空間複雜度：

轉移優化

根據轉移的依賴關系，實作上，我們并不需要真正記錄每一個 ，而可以直接記錄一個總的不同子序列方案數 ​​

​ans​

​。

這可以避免每次計算新狀态時，都累加前一個

Java 代碼：

class Solution {
    int MOD = (int)1e9+7;
    public int distinctSubseqII(String s) {
        int n = s.length(), ans = 0;
        int[] f = new int[26];
        for (int i = 0; i < n; i++) {
            int c = s.charAt(i) - 'a', prev = f[c];
            f[c] = (ans + 1) % MOD;
            ans = (ans + f[c]) % MOD;
            ans = (ans - prev + MOD) % MOD;
        }
        return      

TypeScript 代碼：

function distinctSubseqII(s: string): number {
    const MOD = 1e9+7
    let n = s.length, ans = 0
    const f = new Array<number>(26).fill(0)
    for (let i = 0; i < n; i++) {
        const c = s.charCodeAt(i) - 'a'.charCodeAt(0), prev = f[c]
        f[c] = (ans + 1) % MOD
        ans = (ans + f[c]) % MOD
        ans = (ans - prev + MOD) % MOD
    }
    return      

Python 代碼：

class Solution:
    def distinctSubseqII(self, s: str) -> int:
        n, MOD, ans = len(s), 1e9+7, 0
        f = [0] * 26
        for i in range(n):
            c = ord(s[i]) - ord('a')
            prev = f[c]
            f[c] = (ans + 1) % MOD
            ans = (ans + f[c] - prev) % MOD
        return int(ans)      

• 時間複雜度：
• 空間複雜度：

最後

這是我們「刷穿 LeetCode」系列文章的第 ​

​No.940​

​ 篇，系列開始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道題目，部分是有鎖題，我們将先把所有不帶鎖的題目刷完。

在這個系列文章裡面，除了講解解題思路以外，還會盡可能給出最為簡潔的代碼。如果涉及通解還會相應的代碼模闆。