DSA homework 5 演習課

tags: Course DSA

https://reurl.cc/y4yz2

目錄

• Top down VS Bottom up
• 解決一個 DP 問題

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

• 多以迴圈實作
• 由較小的子問題算出較大的子問題
• 特性：程式碼簡潔、比較不直觀

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

• 以遞迴計算子問題的答案
• 由較大的子問題遞迴算出較小的子問題
• 記憶化搜索：每個子問題只計算一次
• 特性：接近思考方式、實作直觀

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)\)

解決一個 DP 問題

1. 找有同樣結構的子問題
2. 訂定狀態 & 狀態轉移
3. 計算複雜度
4. AC？

找有同樣結構的子問題

• 一個 \(N \times M\)的方格紙可做的操作：
  • 撕掉一行
  • 撕掉一列
• 變成比較小張的方格紙片，發現方格紙片：
  • 是原本方格紙的連續區域
  • 適用相同的規則(子問題)

訂定狀態 & 狀態轉移

• 目前子問題： 一張方格紙片的答案 (方法數)
• 目前的狀態： \((L_1, R_1, L_2, R_2)\)
  • 目的：表達方格紙片的資訊
  • \(L_1, R_1\)：在原先方格紙上的 \([L_1, R_1]\) 行
  • \(L_2, R_2\)：在原先方格紙上的 \([L_2, R_2]\) 列
  • 整張紙就是 \((1, M, 1, 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\)

種撕的方法

總結

執行 \(K\) 次的方法
\(=\sum_{所有可能的一次}\) 執行 \(K - 1\) 次的方法

總結

\(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

複雜度分析

• 統一以 \(N\) 表示：
• 狀態複雜度：\((L_1, R_1, L_2, R_2, K)\)
  • 數量級\((N, N, N, N, N^2) = O(N^6)\)
  • \(K\) 的量級： \(O(N^2)\)
• 轉移複雜度：枚舉\((X, K_A)\)
  • 數量級\((N, N^2) = O(N^3)\)
  • \(0 <= K_A <= K - 1\)
• 整體複雜度： \(O(N^9)\)
  • 本題常數很小