DSA homework 5 演習課

Top down VS Bottom up

以計算組合數 \(C_{m}^{n}\) 為例：

• 計算 \(0 \le m \le n \le 1000\) 的所有 \(C_{m}^n \% 10^9+7\)

• Pascal's rule

  • \(\displaystyle C_{m}^{n} = C_{m}^{n - 1} + C_{m - 1}^{n - 1}\)

名詞定義

• 狀態：以 \((n, m)\) 兩個數字表示 \(C_{m}^{n}\)
• 轉移：狀態和狀態之間的關係
  • \(C_{m}^{n} = C_{m}^{n - 1} + C_{m - 1}^{n - 1}\)
• DP 複雜度：
  • \(O(狀態複雜度 \times 轉移複雜度)\)
  • \(有多少東西要算 \times 算一個要多久\)

Bottom up - code

int c[max][max], mod = 1000000007;
for(int n = 0; n <= 1000; n ++){
    for(int m = 0; m <= n; m ++){
        if(n == m || m == 0)
            c[n][m] = 1;
        else
            c[n][m] = (c[n - 1][m] + c[n - 1][m - 1]) % mod;
    }
}

Top down - code

int c[max][max], solved[max][max]; // init solved false

int C(int n, int m){
    if(solved[n][m] == true) return c[n][m];
    
    solved[n][m] = true;
    
    if(n == m || m == 0) 
        return c[n][m] = 1;
    else 
        return c[n][m] = (C(n - 1, m) + C(n - 1, m - 1)) % mod;
}

記憶化搜索 or not

• 有記憶化搜索：
  • 每個狀態 \(C(n, m)\) 只會被計算一次
  • 總複雜度：\(O(n^2)\)
• 沒有有記憶化搜索：
  • 算 \(C(n, m)\) 時間複雜度為 \(O(C^n_{m})\)
  • 總複雜度：\(O(2^n)\)

紙片\((L_1, R_1, L_2, R_2)\) ->

• A紙片：\((L_1, X - 1, L_2, R_2)\)
• B紙片：\((X + 1, R_1, L_2, R_2)\)
• 讓 \(V_A=Ans(A紙片), V_B=Ans(B紙片)\)
  可以合併答案嗎
  • \(V_A \times V_B?\) No, 可以交互撕

不能合併答案，A、B兩張紙片可能會產生交互影響

增加會撕掉幾個步驟，紙片總共撕 K 次

增加狀態的維度：

從 \((L_1, R_1, L_2, R_2)\)
變 \((L_1, R_1, L_2, R_2, K)\)

紙片\((L_1, R_1, L_2, R_2, K)\) ->

• A紙片：\((L_1, X - 1, L_2, R_2, K_A)\)
• B紙片：\((X + 1, R_1, L_2, R_2, K - 1 - K_A)\)
  其中 \(0 <= K_A <= K - 1\)

可以轉移

紙片\((L_1, R_1, L_2, R_2, K)\) ->

• \(V_A = Ans(L_1, X - 1, L_2, R_2, K_A)\)
• \(V_B = Ans(X + 1, R_1, L_2, R_2, K - 1 - K_A)\)

則選擇第 \(X\) 行撕下去後，剩下的的 \(K - 1\) 次會有

\(\displaystyle C^{K - 1}_{K_A} \times V_A \times V_B\)

種撕的方法

總結

\(Ans(L_1, R_1, L_2, R_2, K)=\sum_X\sum_{K_A} C^{K - 1}_{K_A} \times\)
\(Ans(紙片A,K_A) \times Ans(紙片B,K - 1 - K_A)\)

• 其中 \(X\) 為滿足條件的撕法(包含行、列)

Final Ans： \(\sum_K Ans(1, M, 1, N, K)\)

注意事項 ?

• \((L_1, R_1, L_2, R_2, K)\)遞迴要到甚麼時候停下來
• \(K = 0\)
• 已經不能撕了
• 讓數值保持在 \([0, 10^9+7)\)
  • 計算過程 long long