如何解决leetcode中完全平方数的问题-快上网网站建设公司

如何解决leetcode中完全平方数的问题

这篇文章主要为大家展示了“如何解决leetcode中完全平方数的问题”，内容简而易懂，条理清晰，希望能够帮助大家解决疑惑，下面让小编带领大家一起研究并学习一下“如何解决leetcode中完全平方数的问题”这篇文章吧。

青阳网站制作公司哪家好，找创新互联！从网页设计、网站建设、微信开发、APP开发、响应式网站开发等网站项目制作，到程序开发，运营维护。创新互联从2013年成立到现在10年的时间，我们拥有了丰富的建站经验和运维经验，来保证我们的工作的顺利进行。专注于网站建设就选创新互联。

题目链接

https://leetcode-cn.com/problems/perfect-squares/

题目描述

给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。

示例 1:

输入: n = 12
输出: 3
解释: 12 = 4 + 4 + 4.

示例 2:

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

解题方案

思路

标签：动态规划
首先初始化长度为n+1的数组dp，每个位置都为0
如果n为0，则结果为0
对数组进行遍历，下标为i，每次都将当前数字先更新为最大的结果，即dp[i]=i，比如i=4，最坏结果为4=1+1+1+1即为4个数字
动态转移方程为：dp[i] = MIN(dp[i], dp[i - j * j] + 1)，i表示当前数字，j*j表示平方数
时间复杂度：O(n*sqrt(n))，sqrt为平方根

代码

Java版本

class Solution {
   public int numSquares(int n) {
       int[] dp = new int[n + 1]; // 默认初始化值都为0
       for (int i = 1; i <= n; i++) {
           dp[i] = i; // 最坏的情况就是每次+1
           for (int j = 1; i - j * j >= 0; j++) {
               dp[i] = Math.min(dp[i], dp[i - j * j] + 1); // 动态转移方程
           }
       }
       return dp[n];
   }
}

JavaScript版本

/**
* @param {number} n
* @return {number}
*/
var numSquares = function(n) {
   const dp = [...Array(n+1)].map(_=>0); // 数组长度为n+1，值均为0
   for (let i = 1; i <= n; i++) {
       dp[i] = i; // 最坏的情况就是每次+1
       for (let j = 1; i - j * j >= 0; j++) {
           dp[i] = Math.min(dp[i], dp[i - j * j] + 1); // 动态转移方程
       }
   }
   return dp[n];
};