m*n长方形中正方形最少个数 java

同样地，要求 m*n 的长方形中最少需要多少个正方形来填满，我们可以使用动态规划的思想，令 dp[i][j] 表示填满 i*j 的长方形最少需要的正方形个数。

状态转移方程为：

dp[i][j] = min(dp[i-k][j]+dp[k][j-k])，其中 1<=k<=i/2

dp[i][j] = min(dp[i][j-k]+dp[i-k][k])，其中 1<=k<=j/2

初始状态为 dp[i][i] = 1，dp[i][j] = Integer.MAX_VALUE，其中 Integer.MAX_VALUE 表示一个很大的数。

最终答案为 dp[m][n]。

以下是用 Java 实现的代码：

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    private static final int N = 505;
    private static int[][] dp = new int[N][N];

    private static int min(int a, int b) {
        return a < b ? a : b;
    }

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int m = scan.nextInt();
        int n = scan.nextInt();
        scan.close();

        for(int[] row : dp) {
            Arrays.fill(row, Integer.MAX_VALUE);
        }
        for(int i = 1; i <= Math.max(m, n); i ++) {
            dp[i][i] = 1;
        }

        for(int i = 1; i <= m; i ++) {
            for(int k = 1; k <= i / 2; k ++) {
                dp[i][n] = min(dp[i][n], dp[i-k][n] + dp[k][n-i+k]);
            }
        }

        for(int j = 1; j <= n; j ++) {
            for(int k = 1; k <= j / 2; k ++) {
                dp[m][j] = min(dp[m][j], dp[m][j-k] + dp[m-k][k]);
            }
        }

        System.out.println(dp[m][n]);
    }
}