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\mathrm{\%}{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(\mathrm{狀}\mathrm{態}\mathrm{複}\mathrm{雜}\mathrm{度}\times \mathrm{轉}\mathrm{移}\mathrm{複}\mathrm{雜}\mathrm{度})$
  • $\mathrm{有}\mathrm{多}\mathrm{少}\mathrm{東}\mathrm{西}\mathrm{要}\mathrm{算}\times \mathrm{算}\mathrm{一}\mathrm{個}\mathrm{要}\mathrm{多}\mathrm{久}$

---

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_m^n)$
  • 總複雜度：
    $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\mathrm{紙}\mathrm{片}),V_B=Ans(B\mathrm{紙}\mathrm{片})$
  可以合併答案嗎
  • $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_A}^{K-1}\times V_A\times V_B}$

種撕的方法

---

總結

---

執行

$K$ 次的方法

$=\sum _{\mathrm{所}\mathrm{有}\mathrm{可}\mathrm{能}\mathrm{的}\mathrm{一}\mathrm{次}}$ 執行

$K-1$ 次的方法

---

總結

---

$Ans(L_1,R_1,L_2,R_2,K)=\sum _X\sum _{K_A}{C}_{K_A}^{K-1}\times$

$Ans(\mathrm{紙}\mathrm{片}A,K_A)\times Ans(\mathrm{紙}\mathrm{片}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)$
  • 本題常數很小