完全平方数 Posted on 2021-06-12 00:00:00 2021-06-26 00:00:00 by Author 摘要 给定正整数 n，找到若干个完全平方数,使得组成n的完全平方数的个数最少(你能找到吗) # 完全平方数 1. 题目描述 - 给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。给你一个整数 n ，返回和为 n 的完全平方数的 最少数量 。 完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。 2. 示例描述 - 示例一 - 输入：n = 12 - 输出：result = 3 - 解释：12 = 4 + 4 + 4 - 示例二： - 输入：n = 13 - 输出：result = 2 - 解释：13 = 4 + 9 3. 解题思路 - 这是第一次做出来一个dp的题，感觉非常nice,从前都是看别人的解法做的，看别人的解法，一看就会，自己动手做就废。 - 就我这道题而言来说，我上来就定义了一个`N+1`*`N+1`二维数组，然后在写代码的时候发现不知道二维数组的每个下标的值代表是什么，还有二维数组每个位置的值是什么意思。大概想了十几分钟也没想出个头绪。所以换成了长度为`n+1`的一维数组。然后确定一维数组下标的意义，和该位置所代表的意义。 - 这里我规定下标i就是任意给定的一个数，那么dp[i]所代表的意义就是组成i所需要最少的完全平方数的个数。那么给定一个数n,那么dp[n]就是组成n所需要最少的完全平方数的个数。 - 对于解dp的题目来说，首先我们要理解我们定义dp数组每个位置的含义，其次就是初始化dp数组，再者就是找递推公式，最后在写代码。上面我们了解了dp数组每个位置的含义，那么接下来我们怎么样初始化dp数组尼。对于下标为0的位置，我们知道0=0×0,所以dp[0]=1,即组成0所需要最少的完全平方数个数为0。接下来就是确定递推公式，由于我们知道对于每一个大于1的数，都可以由前一个数加1得到，及就是`j =( j-1)+1`，那么对于`dp[j]`可以有`dp[j-1]+1`,因为`j-(j-1)=1`，那么我们为了得到一个一般的规律，我们可以这样想，假设`j =i×i+1`，那么`dp[j]`是不是可以由`dp[j-i×i]+1`的到尼,因为`j-i×i =1`,由于要找组成一个数最少的完全平方数的个数，那么递推公式为 `dp[j] = min(dp[j-i*×i]+1,dp[j])`,解释一下递推公式为什么这么写，对于j这个数来说，组成这个数的完全平方数有可能有多种，我们想办法找出其中个数最少的一种，我们知道dp[j]是由dp[j-1]推到出来的，所以要得到dp[j]，必须知道dp[j-1]，所以我们初始化dp数组的时候，让其每个位置都为Integer.MAX_VALUE,这样`dp[j] = min(dp[j-i*×i]+1,dp[j])`，就能从前一个数所得到。讲到这里我自己感觉自己讲的也是有点模棱两可了。可能自己心里知道是什么意思，但是就是表达不出来，这可能就是只可意会不可言传吧。等到以后自己表达能力强了以后，再来修改这篇文章吧，具体代码示例如下。 4. 代码实现 ```java public int numSquares(int n) { //首先定义一个长度为n+1的一维数组 //为什么不定义一个长度为n的一维数组 //因为数组下标是从0开始的,如果定义一个长度为n的一维数组 //那么只能访问dp[n-1]，而这个值代表组成n-1这个数所需要最少完全平方数的个数 //而我们题目需要的是组成n这个数所需要的最少完全平方数的个数，所以定义一个长度为n+1的一维数组 int[] dp = new int[n + 1]; //对于0来说0 = 0*0 ，所以dp[0]=1 dp[0] = 1; //对于其他的数，我们先赋值为最大值 //由于我们要找到最少的，所以先赋值最大的 //如果要找打最多的，那么我们就可以先赋值最小的 //这个思想在许多题目都有体现。 for (int i = 1; i <= n; i++) { dp[i] = Integer.MAX_VALUE; } for (int i = 1; i < Math.sqrt(n); i++) { //对于i*i这个数，组成i*i这个数所需要最少的完全平方数个数，那么肯定为1呀 dp[i * i] = 1; //接下来就是精华部分 for (int j = i * i + 1; j <= n; j++) { //对于j这个数由于j是从i*i+1开始，那么j-i*i==1,那么dp[j]就需要从前一个数所得到。 //这里为什么要一层循环尼，因为我们要找到组成j这个数需要最少的完全平方数个数， // 而组成j这个数，包含i*i（i这个数是个变量）,我们要找到从1到sqrt(j)，组成j所需要最少的完全平方数的个数 // 所以要多一层循环 dp[j] = Math.min(dp[j - i * i] + 1, dp[j]); } } return dp[n]; } ```
{{ item.content }}
{{ child.content }}