PerfectSquareNumber题目描述：给定一个正整数n，找出几个完全平方数（比如1,4,9,16,...）使得它们的和等于n.您需要尽量减少构成总和的完全正方形的数量。给定一个整数n，返回总和为n的最小完全平方数。完美平方是一个整数，其值等于另一个整数的平方；换句话说，其值等于整数乘以自身的乘积。例如，1、4、9和16都是完全正方形，但3和11则不是。例子见LeetCode官网。来源：LeetCode链接：https://leetcode-cn.com/probl...版权归LeetCode所有。商业转载请联系官方授权，非商业转载请注明出处。解法一：动态规划通过动态规划求解。首先初始化一个dp数组，记录每一位可以有的最小幂数和累加数，然后将每一位的值初始化为最大值，以备后用。进行比较，然后核心逻辑就是下面的遍历过程：第i位的幂和可以由i->jj步加上jj位幂和的步数组成，然后进行比较每次判断较小的值作为第i位的个数。说明：看了网上的基于数理逻辑的分析求解过程，重在分析。很简单，就是没看懂。原来通过数学分析，最多只有几种情况，然后根据这几种情况进行判断。publicclassLeetCode_279{/***动态规划**@paramn*@return*/publicstaticintnumSquares(intn){//记录每个位的最小幂数和累加数int[]dp=newint[n+1];for(inti=1;i<=n;i++){//将每个数字初始化为最大值dp[i]=Integer.MAX_VALUE;}//从1开始遍历for(inti=1;i<=n;i++){for(intj=1;j*j<=i;j++){if(i>=j*j){//这里的逻辑是第i位的幂和可以由步数i->j*j加上第j*j位的幂和的步数组成，然后每次比较较小的值判断为第i位数字的个数dp[i]=Math.min(dp[i],dp[i-j*j]+1);}}}返回dp[n];}publicstaticvoidmain(String[]args){//测试测试用例1，预期输出：3（从4+4+4获得）System.out.println(numSquares(12));//测试用例2，预期输出：2（从4+9获得）System.out.println(numSquares(13));}}【每日寄语】学习丰富知识，知识提升才华，使人创造业绩。
