每日一题 279完全平方数（完全背包）

题目

完全平方数
给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。

完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

示例 1：

输入：n = 12
输出：3
解释：12 = 4 + 4 + 4
示例 2：

输入：n = 13
输出：2
解释：13 = 4 + 9

提示：

1 <= n <= 104

题解

记忆化搜索

class Solution {private int[][] cache;public int numSquares(int n) {// if (n == 1) {//     return 1;// }int len = (int) Math.sqrt(n);cache = new int[len][n + 1];for (int i = 0; i < len; i++) {Arrays.fill(cache[i],-1);}int ans = dfs(len - 1, n);return ans < Integer.MAX_VALUE / 2 ? ans : -1;}public int dfs(int i, int c) {if (i < 0) {return c == 0 ? 0 : Integer.MAX_VALUE / 2;}if (cache[i][c] != -1) {return cache[i][c];}if (c < (i + 1) * (i + 1)) {return cache[i][c] = dfs(i - 1, c);}return cache[i][c] = Math.min(dfs(i - 1, c), dfs(i, c - (i + 1) * (i + 1)) + 1);}
}

递推

class Solution {public int numSquares(int n) {int len = (int)Math.sqrt(n);int[][] f = new int[2][n + 1];Arrays.fill(f[0], Integer.MAX_VALUE / 2);f[0][0] = 0;for (int i = 0; i < len; i++) {for (int c = 1; c <= n; c++) {if (c < (i + 1) * (i + 1)) {f[(i + 1)%2][c] = f[i%2][c];} else {f[(i + 1)%2][c] = Math.min(f[i%2][c],f[(i + 1)%2][c - (i + 1) * (i + 1)] + 1);}}}int ans = f[len%2][n];return ans < Integer.MAX_VALUE / 2 ? ans : -1;}
}

两个数组优化

class Solution {public int numSquares(int n) {int len = (int)Math.sqrt(n);int[][] f = new int[2][n + 1];Arrays.fill(f[0], Integer.MAX_VALUE / 2);f[0][0] = 0;for (int i = 0; i < len; i++) {for (int c = 1; c <= n; c++) {if (c < (i + 1) * (i + 1)) {f[(i + 1)%2][c] = f[i%2][c];} else {f[(i + 1)%2][c] = Math.min(f[i%2][c],f[(i + 1)%2][c - (i + 1) * (i + 1)] + 1);}}}int ans = f[len%2][n];return ans < Integer.MAX_VALUE / 2 ? ans : -1;}
}

一个数组优化

class Solution {public int numSquares(int n) {int len = (int)Math.sqrt(n);int[] f = new int[n + 1];Arrays.fill(f, Integer.MAX_VALUE / 2);f[0] = 0;for (int i = 0; i < len; i++) {for (int c = (i + 1) * (i + 1); c <= n; c++) {f[c] = Math.min(f[c],f[c - (i + 1) * (i + 1)] + 1);}}int ans = f[n];return ans < Integer.MAX_VALUE / 2 ? ans : -1;}
}