題目網址：https://leetcode.cn/problems/valid-permutations-for-di-sequence/

題意：給一長度為 n 的 string s , 其中 s[i] 可能是：

  • D 代表減少
  • I 代表增加

有效排列是對在 [0, n]  範圍內的所有整數的一個排列 perm, 使得對所有的 i 滿足以下規則：

  • 若 s[i] == 'D', 則 perm[i] > perm[i + 1]
  • 若 s[i] == 'I', 則 perm[i] < perm[i + 1]

返回有效排列 perm 的數量, 因為答案可能很大, 所以請返回你的答案對 $10^9 + 7$ 取餘數。

Solution 1：

想法：利用 DP, 由於 s[i] 決定的只是 perm 中的「相對」大小, 故 perm[i] 的值僅由 s[i - 1] 和 perm[i - 1] 決定。

1. 定義狀態：

  • 首先, 會在 s 前先加上一個 #, 代表什麼元素都沒有的狀態
  • dp[i][j]：s[1:i] 中, 結尾為 perm[i] = j 的有效排列數。其中 0 ≤ j ≤ i
    ➔ 相當於是 [0, i] 的有效排列數

2. 得到轉移方程：

  • 若 s[i] == 'I', 因 perm[i] = j, 所以有效排列數為加總前一個數 s[i - 1] 在區間 [0, j - 1] 的有效排列數
    ➔ dp[i][j] = sum(dp[i - 1][k]), for 0 ≤ k ≤ j - 1
  • 若 s[i] == 'D', 因 perm[i] = j, 那有效排列數是不是為加總前一個數 s[i - 1] 在區間 [j + 1, i] 的有效排列數呢？其實不是, s[i - 1] 要改成在區間 [j, i] 才對
    ➔ dp[i][j] = sum(dp[i - 1][k]), for j ≤ k ≤ i

    • 理由如下, 假如我們現在已經有了一個 "DID" 的排列 1032。若我們還想加一個 D, 將其變成 "DIDD" 的排列, 應該如何加數字呢？多了一個數字 4, 但顯然直接加 4 是不行的

      • 可以在末尾加 2, 但是要先把原排列中 ≥ 2 的數字都先 +1, 即 1032 ➔ 1043, 然後再加 2, 變成 10432
      • 也可以在末尾加 1, 但是要先把原排列中 ≥ 1 的數字都先 +1, 即 1032 ➔ 2043, 然後再加 1, 變成 20431
      • 也可以在末尾加 0, 但是要先把原排列中 ≥ 0 的數字都先 +1, 即 1032 ➔ 2143, 然後再加 0, 變成 21430
      • 但是, 無法再末尾加 3 或 4, 因為原排列中的最後一位為 2, 所以只有 ≤ 2 的數能被加在末尾, 否則無法形成降序（s = "DIDD", 最後必須是降序）

      ➔ 故 k 的區間為 [j, i], 其中 j 為原排列的末尾 perm[i - 1] 之值

3. 初始化：

  • dp[0][0]：當範圍為 [0, 0] 時, 只有 1 種有效排列數
    ➔ dp[0][0] = 1
  • 其餘皆初始成 0

題目要求的是所有有效的排列數, 故答案為加總最後一位所有的可能性

class Solution {
public:
    int numPermsDISequence(string s) {
        const int n = s.size(), mod = 1e9 + 7;
        vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0));

        dp[0][0] = 1;
        s = '#' + s;

        for (int i = 1; i <= n; ++i) {
            for (int j = 0; j <= i; ++j) {
                if (s[i] == 'I') {
                    for (int k = 0; k <= j - 1; ++k) {
                        dp[i][j] = (dp[i][j] + dp[i - 1][k]) % mod;
                    }
                } else {
                    for (int k = j; k <= i - 1; ++k) {
                        dp[i][j] = (dp[i][j] + dp[i - 1][k]) % mod;
                    }
                }
            }
        }

        // 有效排列數為加總最後一位的所有可能性
        int res = 0;
        for (int j = 0; j <= n; ++j) {
            res = (res + dp[n][j]) % mod;
        }

        return res;
    }
};
  • time：$O(n^2)$ ➔ for loop
  • space：$O(n^2)$ ➔ dp

Solution 2：

想法：改進 Solution 1, 由於 dp[i][j] 只會用到上一列的狀態, 故只需儲存上一列的狀態即可

class Solution {
public:
    int numPermsDISequence(string s) {
        const int n = s.size(), mod = 1e9 + 7;
        vector<int> dp(n + 1, 0);

        dp[0] = 1;
        s = '#' + s;

        for (int i = 1; i <= n; ++i) {
            const auto prevRow = dp; // 記住上一列的狀態
            dp = vector<int>(n + 1, 0); // 因為 dp[j] 要加總, 故加總前要先清除舊值

            for (int j = 0; j <= i; ++j) {
                if (s[i] == 'D') {
                    for (int k = j; k <= i - 1; ++k) {
                        dp[j] = (dp[j] + prevRow[k]) % mod;
                    }
                } else {
                    for (int k = 0; k <= j - 1; ++k) {
                        dp[j] = (dp[j] + prevRow[k]) % mod;
                    }
                }
            }
        }

        // 有效排列數為加總最後一位的所有可能性
        int res = 0;
        for (int j = 0; j <= n; ++j) {
            res = (res + dp[j]) % mod;
        }

        return res;
    }
};
  • time：$O(n^2)$ ➔ for loop
  • space：$O(n)$ ➔ dp, prevRow