问题背景

给你一个整数 $n$，返回 和为 $n$ 的完全平方数的最少数量 。
完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，$1,4,9$ 和 $16$ 都是完全平方数，而 $3$ 和 $11$ 不是。

数据约束

• $1\le n\le 10^4$

解题过程

动态规划，用两个状态：$i$ 表示当前枚举的完全平方数的算数平方根，$j$ 表示剩余的和。
这样一来，状态转移方程就可以表示为$dfs(i,j)=\{\begin{array}{ll}dfs(i-1,j)& j<i^2\\ min(dfs(i-1,j),dfs(j-i^2)+1)& j\le i^2\end{array}$。
递归入口 是 $dfs(\lfloor \sqrt{n}\rfloor ,n)$，表示初始枚举的最大数为 $\sqrt{n}$，剩余的和为 $n$。
递归边界 是 $dfs(0,0)=0$，表示没有剩余的数可选，且和刚好为零。

翻译成递推之后，由于计算时只用到前一个状态，记忆化数组可以去掉一个维度。
递推的计算可以放在静态代码块里，给所有测试用例公用。

具体实现

递归

class Solution {private static final int[][] memo = new int[110][10010];static {for (int[] row : memo) {Arrays.fill(row, -1);}}public int numSquares(int n) {return dfs((int) Math.sqrt(n), n);        }private int dfs(int i, int j) {if (i == 0) {return j == 0 ? 0 : Integer.MAX_VALUE;}if (memo[i][j] != -1) {return memo[i][j];}if (j < i * i) {return memo[i][j] = dfs(i - 1, j);}return memo[i][j] = Math.min(dfs(i - 1, j), dfs(i, j - i * i) + 1); }
}

递推

class Solution {private static final int MAX_N = 10000;private static final int[][] dp = new int[110][MAX_N + 1];static {Arrays.fill(dp[0], Integer.MAX_VALUE);dp[0][0] = 0;for (int i = 1; i * i <= MAX_N; i++) {for (int j = 0; j <= MAX_N; j++) {if (j < i * i) {dp[i][j] = dp[i - 1][j];} else {dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - i * i] + 1);}}}}public int numSquares(int n) {return dp[(int) Math.sqrt(n)][n];    }
}

空间优化

class Solution {private static final int MAX_N = 10000;private static final int[] dp = new int[MAX_N + 1];static {Arrays.fill(dp, Integer.MAX_VALUE);dp[0] = 0;for (int i = 1; i * i <= MAX_N; i++) {for (int j = i * i; j <= MAX_N; j++) {dp[j] = Math.min(dp[j], dp[j - i * i] + 1);}}}public int numSquares(int n) {return dp[n];    }
}