# 【題解】TIOJ 2020 . E.艾迪摺紙趣

【題目敘述】https://tioj.ck.tp.edu.tw/problems/2020
【題目敘述】http://www.tcgs.tc.e
du.tw:1218/ShowProblem?problemid=h172
【解題想法】DP + 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))
```