Permutation ที่ถูกต้องสำหรับลำดับ DI ใน C++

คำอธิบายปัญหา

ให้สตริง S ประกอบด้วย 'D' (decreasing) และ 'I' (increasing) หาจำนวน permutation P ของ {0..n} ที่ทำให้ ∀i: S[i]=='D' ⇒ P[i]>P[i+1], S[i]=='I' ⇒ P[i]

ตัวอย่าง

S = "IDD" → Output: 3
Permutations: (0,3,2,1), (1,3,2,0), (2,3,1,0)

แนวทางแก้ปัญหา: Dynamic Programming

State: dp[i][j] = จำนวนวิธีจัดเรียง i+1 ตัวแรก ที่จบด้วยจำนวนที่เป็น "อันดับ j" ในจำนวนที่เหลือ (relative rank)

Transition:

• S[i]=='I': dp[i+1][j] = Σ dp[i][k] สำหรับ k=0..j (prefix sum)
• S[i]=='D': dp[i+1][j] = Σ dp[i][k] สำหรับ k=j..n-i-1 (suffix sum)

ใช้ตัวแปร curr สะสม prefix/suffix sum เพื่อลดเป็น O(1) ต่อ state

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9+7;

class Solution {
public:
    int numPermsDISequence(string S) {
        int n = S.size();
        vector<vector<int>> dp(n+1, vector<int>(n+1, 0));
        for(int j=0; j<=n; j++) dp[0][j] = 1;
        
        for(int i=0; i=0; j--) {
                    cur = (cur + dp[i][j+1]) % MOD;
                    dp[i+1][j] = (dp[i+1][j] + cur) % MOD;
                }
            }
        }
        return dp[n][0];
    }
};

ความซับซ้อน

• เวลา: O(n²)
• พื้นที่: O(n²) (ลดเป็น O(n) ได้)