写点什么

LeetCode 题解:279. 完全平方数,动态规划,JavaScript,详细注释

用户头像
Lee Chen
关注
发布于: 2021 年 03 月 07 日
LeetCode题解:279. 完全平方数,动态规划,JavaScript,详细注释

原题链接:279. 完全平方数


解题思路:


  1. 本题类似于322. 零钱兑换,如果你对322. 零钱兑换不熟悉,可以先看[题解](https://leetcode-cn.com/problems/coin-change/solution/leetcodeti-jie-322-ling-qian-dui-huan-do-etlo/)。二者的区别是硬币种类不固定,在本题中,对于当前金额i,硬币种类为小于i的完全平方数。

  2. 该题递推的是从1开始,使用小于i完全平方数,计算能够凑到i的最小数量,由此不断累加到n的过程。

  3. 创建一个长度为n + 1dp数组,用索引就表示从0n的数字。

  4. 对于当前数字i,我们可以用for (let j = 1; j * j <= i; j++) {},计算出小于i的完全平方数。

  5. i是由i - j * j用 1 个j * j凑过来,同时要保证它是所有结果中最小的一个,因此状态转移返程为:dp[i] = Math.min(dp[i], dp[i - j * j] + 1);


/** * @param {number} n * @return {number} */var numSquares = function (n) {  // 需要计算到n,因此需要从0开始递推到n  // 由于要计算的是最小值,因此初始化为Infinity,避免计算错误  let dp = new Array(n + 1).fill(Infinity);  dp[0] = 0; // 0对应的可组合数字为0
// 从1开始才会有组合个数,一直递推到n for (let i = 1; i < dp.length; i++) { // 每次计算可用的完全平方数 // 判断可用的方法是j*j不超过当前数量i for (let j = 1; j * j <= i; j++) { // 因为j * j <= i,所以i - j * j不可能小于0,无需判断 dp[i] = Math.min( dp[i], // 当前已储存了之前完全平方数的组合数量 // 当前的完全平方数数量,可由i - j * j加一个j * j而来 // 因此等于dp[i - j * j]的数量加1个j * j dp[i - j * j] + 1, ); } }
// 递推到n时,就计算出了所有可能的数量 return dp[n];};
复制代码


发布于: 2021 年 03 月 07 日阅读数: 12
用户头像

Lee Chen

关注

还未添加个人签名 2018.08.29 加入

还未添加个人简介

评论

发布
暂无评论
LeetCode题解:279. 完全平方数,动态规划,JavaScript,详细注释