思路

1. 转化为完全背包问题
   • $N$为最大总面积，蛋糕边长为 $1 \sim \lfloor \sqrt N \rfloor$，价值为1，个数不限
   • $f(i, j) = min(f(i-1, j), f(i, j-v)+1)$
2. 因为求的是最小值，所以f[i][j]初始化使用Integer.MAX_VALUE或者足够大的数
3. f[0][0]初始值设为0，表示不选择任何蛋糕且总面积为0的需要蛋糕最小个数为0

代码 二维

import java.lang.*;
import java.util.*;

public class Main {
    static Scanner scanner = new Scanner(System.in);

    static int t, n;
    static int[][] f = new int[110][100010];

    public static void main(String[] args) {
        t = scanner.nextInt();
        for (int k = 1; k <= t; k++) {
            int m = scanner.nextInt();
            n = (int) Math.sqrt(m);
            for (int i = 0; i <= n; i++) {
                for (int j = 0; j <= m; j++) {
                    f[i][j] = Integer.MAX_VALUE;
                }
            }
            f[0][0] = 0;
            for (int i = 1; i <= n; i++) {
                for (int j = 0; j <= m; j++) {
                    f[i][j] = f[i - 1][j];
                    if (j >= i * i) {
                        f[i][j] = Math.min(f[i][j], f[i][j - i * i] + 1);
                    }
                }
            }
            System.out.printf("Case #%d: %d\n", k, f[n][m]);
        }
    }
}

代码 一维

import java.lang.*;
import java.util.*;

public class Main {
    static Scanner scanner = new Scanner(System.in);

    static int t, n;
    static int[] f = new int[100010];

    public static void main(String[] args) {
        t = scanner.nextInt();
        for (int k = 1; k <= t; k++) {
            int m = scanner.nextInt();
            n = (int) Math.sqrt(m);
            Arrays.fill(f, Integer.MAX_VALUE);
            f[0] = 0;
            for (int i = 1; i <= n; i++) {
                for (int j = i * i; j <= m; j++) {
                    f[j] = Math.min(f[j], f[j - i * i] + 1);
                }
            }
            System.out.printf("Case #%d: %d\n", k, f[m]);
        }
    }
}