给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。
示例 1:
输入: n = 12输出: 3 解释: 12 = 4 + 4 + 4复制代码
示例 2:
输入: n = 13输出: 2解释: 13 = 4 + 9复制代码
我的心历路程： 碰到最少、最短这种字眼的话，现在我一开始想到的就是广度优先遍历 + 队列来解决这种类似问题。
思路就用图来解释吧
- 我们把给定的正整数12作为根节点，依次减去符合条件的完全平方数（小于n的完全平方数）
- 减去后得到了 11 8 3 这三个数字，三个数字继续减去 1 4 9 ，又得到了他们的差
- 继续减 1 4 9,直到碰到第一个0为止，说明找到了最短的路径。对应的层数就是最少个数
“Talk is cheap. Show me the code.” --Linus Torvalds
/** * 广度优先搜索，耗时严重，思路： * 1. 计算出可能的完全平方数的数组 * 2. 设置一个数组，初始化元素为传入的正整数 * 3. 设置一个step为0 * 3. 循环这个数组，让数组中的每个元素都删除完全平方数中的每一个元素，第一个差为0的，说明就是最短路径*/var numSquares = function(n) { let MaxSquare = Math.ceil(Math.sqrt(n)); function getAvailableSquareArr(num) { let arr = []; for (let i = 1; i<=num; i++) { arr.push(Math.pow(i, 2)); } return arr; } let squareArr = getAvailableSquareArr(MaxSquare); // 可能的完全平方数组成的数组 let squareLength = squareArr.length; // 完全平方数组长度 let subArr = [n]; // 用来存放每次减去完全平方数的数组,初始值为传入的正整数 let step = 0; while(subArr.length) { step++; let len = subArr.length; for (let j = 0; j < len; j++) { let value = subArr.shift(); // 队首出队列 for (let i = 0; i < squareLength; i++) { let sub = value - squareArr[i]; if (sub === 0) return step; if (sub < 0) { break; } if (!subArr.includes(sub)) { subArr.push(sub); } } } } return step;};复制代码 上面的这种解法我们看一下执行耗时
- 最外层一个while循环
- 内部一个嵌套的for循环
得到时间复杂度为O(n^3)，这里时间复杂度我个人也不大确定是否为O(n^3)，如果您知道怎么算，请在评论解惑。
所以我们需要一种更高效的方式来计算。于是引入了动态规划的方式解决该题。
来自wiki百科：动态规划常常适用于有重叠子问题[1]和最优子结构性质的问题，动态规划方法所耗时间往往远少于朴素解法。动态规划背后的基本思想非常简单。大致上，若要解一个给定问题，我们需要解其不同部分（即子问题），再根据子问题的解以得出原问题的解。
动态规划解决这个问题我也在leecode上看过解释，但是自己就是看不大懂。直到写文章的今天我也还是一知半解。所以使用动态规范解决的方式我现在的水平还讲不清楚，但是我先把动态规划解决的代码放在这，待日后补充具体的思路。各位大佬如果觉得能够讲清楚，也可以在留言处写下自己的思路。带带小弟我。
function numSquares(n) { const dp = [0]; for (let i = 1; i <= n; i++) { dp[i] = Number.MAX_VALUE; for (let j = 1; j*j <= i; j++) { dp[i] = Math.min(dp[i], dp[i-j*j]+1); } } return dp[n];}复制代码