rectangle cutting 281744 29 cses c 2b 2b

1#include <bits/stdc++.h>
2using namespace std;
3
4int main() {
5  int w, h;
6  cin >> w >> h;
7  vector<vector<int>> dp(w+1,vector<int>(h+1));
8  for (int i = 0; i <= w; i++) {
9    for (int j = 0; j <= h; j++) {
10      if (i == j) {
11	dp[i][j] = 0;
12      } else {
13	dp[i][j] = 1e9;
14	for (int k = 1; k < i; k++) {
15	  dp[i][j] = min(dp[i][j], dp[k][j]+dp[i-k][j]+1);
16	}
17	for (int k = 1; k < j; k++) {
18	  dp[i][j] = min(dp[i][j], dp[i][k]+dp[i][j-k]+1);
19	}
20      }
21    }
22  }
23  cout << dp[w][h] << endl;
24}