【題目敘述】https://tioj.ck.tp.edu.tw/problems/2020
【題目敘述】http://www.tcgs.tc.edu.tw:1218/ShowProblem?problemid=h172
【解題想法】DP + Divide & Conquer【筆記】
一開始讀題目，馬上想到的是輾轉相除法，結果就WA了。後來才知道這是經典的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;
}
Python code (credit: Amy Chou)
def kamiori(x, y):
if x == y:
dp[x][y] = 1
return 1
if dp[x][y]:
return dp[x][y]
ret = 1e9
for i in range(1, x):
ret = min(ret, kamiori(i, y) + kamiori(x-i, y))
for i in range(1, y):
ret = min(ret, kamiori(x, i) + kamiori(x, y-i))
dp[x][y] = ret
return ret
N, M = map(int, input().split())
dp = [[0 for j in range(M+1)] for i in range(N+1)]
print(kamiori(N, M))