【筆記】Divide & Conquer 分治法

#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;
}