【筆記】Divide & Conquer 分治法

  • 又稱「 各個擊破法 」。把大問題切割成二或多個小問題, 再把小問題的解答組合成大問題的解答。
  • 【範例】TIOJ 2020 . E.艾迪摺紙趣 【題解
    • 色紙大小為 N × M,問這張色紙最少能切割成幾個正方形?
  • 【做法】
    • dp[x][y]:(初始值為 0) 大小為 x × y 的色紙,最少能切割成的正方形個數,避免重複計算(Line-10)。
    • 函式 kamiori(x, y):遞迴計算 dp[x][y]。
    • 當x = y時,回傳 dp[x][y] = 1,因為本身就是正方形。
    • Line-13,如果遇到已經計算過的dp[x][y],直接讀值,不用重複計算。
    • Line-17 & Line-20:分別從x、y方向開始摺紙,尋找最小值。
  • 【圖例】
    • F(3, 5):大小為 3 × 5 的色紙,最少能切割成的正方形個數.
    • 先沿著 x 方向(垂直方向)開始摺紙,有下面幾種摺法:
      • F(1, 5) + F(2, 5) 或 F(2, 5) + F(1, 5):繼續往下遞迴(把紙摺得更小),直到變成正方形,如F(2, 2)、F(1, 1)。
    • 先沿著 y 方向(水平方向)開始摺紙,有下面幾種摺法:
      • F(3, 1) + F(3, 4) 或 F(3, 2) + F(3, 3) 或 F(3, 3) + F(3, 2) 或 F(3, 4) + F(3, 1):繼續往下遞迴(把紙摺得更小),直到變成正方形,如F(2, 2)、F(1, 1)。
    • 如同利用遞迴計算Fibonacci數列,圖例中的F(x, y)函式會衍生出很多重複的計算,因此要加上 DP 的記憶技巧來縮短程式執行的時間。
#include <iostream>
using namespace std;
 
int N, M;
int dp[105][105];
 
int kamiori(int x, int y) {
    if (x == y) {
        dp[x][y] = 1;
        return 1;
    }
    if (dp[x][y]) return dp[x][y];
     
    int ret = 1e9;
    for (int i=1; i<x; i++)
        ret = min(ret, kamiori(i, y) + kamiori(x-i, y));
     
    for (int i=1; i<y; i++)
        ret = min(ret, kamiori(x, i) + kamiori(x, y-i));
     
    dp[x][y] = ret;
    return ret;
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> N >> M;
    cout << kamiori(N, M) << '\n';
    return 0;
}
分享本文 Share with friends