题目描述

image.png

解题思路

我来把题目翻译一下：完全平方数就是物品（可以无限件使用），凑个正整数n就是背包，问凑满这个背包最少有多少物品？

  • 确定dp数组（dp table）以及下标的含义

dp[j]：和为j的完全平方数的最少数量为dp[j]

  • 确定递推公式

dp[j] 可以由dp[j - i i]推出， dp[j - i i] + 1 便可以凑成dp[j]。
此时我们要选择最小的dp[j]，所以递推公式：dp[j] = min(dp[j - i * i] + 1, dp[j]);

  • dp数组如何初始化

dp[0]表示 和为0的完全平方数的最小数量，那么dp[0]一定是0。
有同学问题，那0 0 也算是一种啊，为啥dp[0] 就是 0呢？
看题目描述，找到若干个完全平方数（比如 1, 4, 9, 16, …），题目描述中可没说要从0开始，dp[0]=0完全是为了递推公式。
非0下标的dp[j]应该是多少呢？
从递归公式dp[j] = min(dp[j - i i] + 1, dp[j]);中可以看出每次dp[j]都要选最小的，所以非0下标的dp[j]一定要初始为最大值，这样dp[j]在递推的时候才不会被初始值覆盖。

  • 遍历顺序

本题不是排列，也不是组合，所以先遍历啥都可以。

  • 举例推导dp数组

已输入n为5例，dp状态图如下：
image.png

  1. public int numSquares(int n) {
  2.     int[] dp = new int[n + 1];
  3.     Arrays.fill(dp, Integer.MAX_VALUE);
  4.     dp[0] = 0;   // 当和为0时，组合的个数为0
  6.     for (int i = 1; i <= n; i++) { // 先遍历物品
  7.         for (int j = i * i; j <= n; j++) {
  8.             if (dp[j - i * i] != Integer.MAX_VALUE) {
  9.                 dp[j] = Math.min(dp[j], dp[j - i * i] + 1);
  10.             }
  11.         }
  12.     }
  14.     return dp[n] == Integer.MAX_VALUE ? 1 : dp[n];
  15. }