The intended solution uses Dynamic Programming.

Let <code>dp[sx][sy][tx][ty]</code> denote the minimum cost to cut the rectangle into <code>1 x 1</code> pieces.

Iterate on the row or column on which you will perform the next cut, after the cut, the current rectangle will be decomposed into two sub-rectangles.