# 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 ``` cpp 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 ``` cpp 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)$ * 本題常數很小