LeetCode 279. 完全平方数
题目描述
给你一个整数 n ,返回和为 n 的完全平方数的最少数量 。
完全平方数 是一个整数,其值等于另一个整数的平方;换句话说,其值等于一个整数自乘的积。例如,1、4、9 和 16 都是完全平方数,而 3 和 11 不是。
示例 1:
输入:n = 12
输出:3
解释:12 = 4 + 4 + 4
示例 2:
输入:n = 13
输出:2
解释:13 = 4 + 9
思路
和LeetCode 322.零钱兑换很类似,这里也是使用动态规划的思路求解。
- 创建dp动态数组,每个索引下标
i
表示组成值i
最少需要几个完全平方数; - 数组初始化:
dp[0]=0
;对于其他每个下标i
,组成值i
最少需要i
个1(1是完全平方数),所以初始化就是让dp[i]=i; - 嵌套循环填充dp数组,第一个for循环遍历从
i~n
,循环体内部求和为n的完全平方数的最少数量; - 第二个for循环遍历的终止条件是
i-j*j>=0
,jj实际上就是完全平方数,j的遍历范围从1开始,每次+1,那么jj的结果就是从1,4,9,16…依次在各个完全平方数内变换。这一点和零钱兑换的那题很类似,实际上就是遍历不超过i的完全平方数(因为完全平方数超过i必不可能组成i,和零钱兑换中的if条件是类似的,如果你的硬币币值>目标金额的话,这个硬币也不可能被用于组成目标金额) - 对于动态转移方程,求的是和为n的完全平方数的最少数量,故dp[i]=Math.min(dp[i],dp[i-j*j]+1),前面也就是不使用完全平方数j时候的结果,后面是使用完全平方数j的结果
- return dp[n];
代码
class Solution {public int numSquares(int n) {int[] dp = new int[n + 1]; // dp数组中的每个下标i表示,组成值i完全平方数的最少数量// 填充dp数组for (int i = 1; i <= n; i++) {dp[i] = i; // 最坏的情况就是,该数由许多1组成,实际上这里设置成Integer.MAX_VALUE也可以for (int j = 1; i - j * j >= 0; j++){// 首先说明for循环的条件为什么是: i-j*j>=0,首先变换一下i>=j*j// j*j实际上就凑成了一个“完全平方数”,在这个for循环里,j的值从1开始,每次不断+1,那么j*j的值就是1,4,9,16...,每次都是完全平方数// 这里实际上就是“假设我们使用这个完全平方数”时// i-j*j中,我们想求i需要多少个完全平方数凑成// 也就是使用了这个完全平方数后的数(j*j是完全平方数,i-j*j是剩余的数值),剩余的数值最少需要由几个完全平方数凑成dp[i] = Math.min(dp[i], dp[i - j * j] + 1);}}return dp[n];}
}