題意#
給你一個長度為 \( n \)、寬度為 \( m \) 的長方形。
你每次操作可以拿刀把其中一塊長方形切成兩塊更小的長方形（長寬必須保持為整數）。請問你最少需要切幾刀，才能把整個大長方形全部切成正方形？
思路#
這是一題標準的「區間 DP」或是分割型 DP。
我們可以建立一個二維陣列 dp，其中 dp[i][j] 代表「要把一個 \( i \times j \) 的長方形完全切成正方形，最少需要的刀數」。
首先思考最簡單的情況：如果這個長方形本來就是正方形（也就是 i == j），那我們連一刀都不用切，答案直接是 0。
如果 i 跟 j 不一樣長，我們就勢必要切一刀把它分成兩半。而這一刀有兩種切法：
- 橫切：我們可以在高度
i的任意位置k切一刀，把它分成上下兩塊，上面是k*j，下面是(i-k)*j。這樣切完的總刀數就是dp[k][j] + dp[i-k][j] + 1。 - 直切：同理，我們可以在寬度
j的任意位置k切一刀，把它分成左右兩塊，左邊是i*k，右邊是i*(j-k)。總刀數則是dp[i][k] + dp[i][j-k] + 1。
我們只要把所有切法（所有的可能 k）都嚐試一遍，從中挑出讓總刀數最少的那一種，並把這個最小值記錄到 dp[i][j] 裡面。透過由小到大的尺寸慢慢推算，最後 dp[n][m] 就會是我們要的答案了。
程式碼#
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define INF LONG_LONG_MAX/1000
#define WA() cin.tie(0)->sync_with_stdio(0)
#define all(x) (x).begin(), (x).end()
#define int long long
#define PII pair<int, int>
signed main() { WA();
int n, m; cin >> n >> m;
// dp[i][j] 代表 i*j 長方形切成正方形的最少刀數
vector<vector<int>> dp(n+1, vector<int>(m+1));
// 初始化極端情況：如果有一邊寬度是 1，長度是多少就只能一塊一塊切，要切長度 - 0 刀 (i-0=i 這裡程式碼將0的部分設為自己，但主要邏輯由 DP 取 min 覆寫)
// （這裡 dp 初始化的概念是防呆用的，更精確的邊界其實是 i == j 時為 0，見迴圈控制）
for (int i = 1; i <= n; i++) dp[i][0] = i;
for (int i = 1; i <= m; i++) dp[0][i] = i;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
// 如果本身就是正方形，不用切，保持預設的 0
if (i == j) continue;
int mn = INF;
// 嘗試所有橫切的可能 (在高度 k 的位置切一刀)
for (int k = 1; k < i; k++) mn = min(mn, dp[i-k][j] + dp[k][j] + 1);
// 嘗試所有直切的可能 (在寬度 k 的位置切一刀)
for (int k = 1; k < j; k++) mn = min(mn, dp[i][j-k] + dp[i][k] + 1);
// 找出所有切法中的最小值
dp[i][j] = mn;
}
}
cout << dp[n][m] << '\n';
}
