#include using namespace std; vector> dp; // i = altura, j = largura // ex 1x3 == (1+ 1x2 + 1x1) int cortedp(int i, int j){ if(dp[i][j] != -1) return dp[i][j]; if(i == j) return 0; int answ = __INT32_MAX__; for(int l = i-1; l > 0; l--){ answ = min(answ, 1+cortedp(i-l, j)+cortedp(l,j)); } for(int r = j-1; r > 0; r--){ answ = min(answ, 1+cortedp(i, j-r)+cortedp(i,r)); } return dp[i][j] = answ; } int main(){ ios::sync_with_stdio(false); int a,b; cin >> a >> b; dp.assign(a+1, vector(b+1, -1)); //cout << cortedp(a,b) << '\n'; Recursiva (AC) for(int i = 1; i <= a; i++){ for(int j = 1; j <= b; j++){ // Calculating rectangle ixj if(i == j){ // Base case, no actions dp[i][j] = 0; }else{ dp[i][j] = __INT32_MAX__; // Vertical cuts for(int k = i-1; k > 0; k--){ dp[i][j] = min(dp[i][j], 1+ dp[i-k][j]+dp[k][j]); } // Horizontal cuts for(int k = j-1; k > 0; k--){ dp[i][j] = min(dp[i][j], 1+ dp[i][j-k]+dp[i][k]); } } } } cout << dp[a][b] << '\n'; return 0; }