Hoán vị hợp lệ cho chuỗi DI trong C++

Cho chuỗi S gồm 'D' (giảm) và 'I' (tăng). Hoán vị P của {0..n} hợp lệ nếu: S[i]=='D' ⇒ P[i] > P[i+1]; S[i]=='I' ⇒ P[i] < P[i+1]. Đếm số hoán vị hợp lệ modulo 10^9+7.

Ví dụ: "IDD" → 3.

Giải thuật

1. DP: dp[i][j] = số cách xếp i+1 số đầu tiên (0..i) sao cho thỏa mãn i ký tự đầu của S, và số cuối cùng là j-th nhỏ nhất trong các số còn lại.
2. Khởi tạo dp[0][j] = 1 (với 1 số, luôn hợp lệ).
3. Duyệt i từ 0 đến n-1:
   • Nếu S[i]=='I': duyệt j từ 0 đến n-i-1, cộng dồn curr = (dp[i][j] + curr) % mod, dp[i+1][j] += curr.
   • Nếu S[i]=='D': duyệt j từ n-i-1 xuống 0, cộng dồn curr = (dp[i][j+1] + curr) % mod, dp[i+1][j] += curr.
4. Kết quả dp[n][0].

Ví dụ mã C++

#include <bits/stdc++.h>
using namespace std;
const int m = 1e9 + 7;
class Solution {
public:
    int numPermsDISequence(string S) {
        int n = S.size();
        vector<vector<int>> dp(n + 1, vector<int>(n + 1));
        for (int j = 0; j <= n; j++) dp[0][j] = 1;
        for (int i = 0; i < n; i++) {
            if (S[i] == 'I') {
                for (int j = 0, curr = 0; j < n - i; j++) {
                    curr = (dp[i][j] + curr) % m;
                    dp[i + 1][j] = (dp[i + 1][j] + curr) % m;
                }
            } else {
                for (int j = n - i - 1, curr = 0; j >= 0; j--) {
                    curr = (dp[i][j + 1] + curr) % m;
                    dp[i + 1][j] = (dp[i + 1][j] + curr) % m;
                }
            }
        }
        return dp[n][0];
    }
};
int main(){
    Solution ob;
    cout << (ob.numPermsDISequence("IDD"));
}

Đầu vào

"IDD"

Đầu ra

3