題目

完全平方數(shù)
給你一個整數(shù) n ，返回 和為 n 的完全平方數(shù)的最少數(shù)量 。

完全平方數(shù) 是一個整數(shù)，其值等于另一個整數(shù)的平方；換句話說，其值等于一個整數(shù)自乘的積。例如，1、4、9 和 16 都是完全平方數(shù)，而 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;}
}

兩個數(shù)組優(yōu)化

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;}
}

一個數(shù)組優(yōu)化

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;}
}