public class SquareSplit {
private int[][] dp;
public int minSquares(int w, int h) {
int a = Math.min(w, h);
int b = Math.max(w, h);
dp = new int[a+1][b+1];
for (int i=0; i<=b; i++) {
dp[0][i] = 0;
dp[1][i] = i;
}
for (int i=2; i<=a; i++) {
for (int j=0; j<=b; j++) {
dp[i][j] = -1;
}
}
return calc(a, b);
}
private int calc(int w, int h) {
int a = Math.min(w, h);
int b = Math.max(w, h);
if (dp[a][b] >= 0) return dp[a][b];
int min = Integer.MAX_VALUE;
for (int i=1; i<=a; i++) {
min = Math.min(min, 1 + calc(a-i, i) + calc(a, b-i));
min = Math.min(min, 1 + calc(b-i, i) + calc(a-i, b));
}
dp[a][b] = min;
return min;
}
}