教育类企业网站磁力搜索器

题目描述

给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。

完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

class Solution {public int numSquares(int n) {int[] nums = new int[102];for(int i = 1; i <= 101; i++){nums[i] = i*i;}int[] dp = new int[n+1];    //dp数组是最后答案，和为n最少个数for(int i = 1; i <= n; i++){dp[i] = i;  //最差的可能是全1for(int j = 1;i-nums[j]>=0;j++){dp[i] = Math.min(dp[i],dp[i-nums[j]]+1);    //轮流用不超过n的完全平方数做替换}}return dp[n];}
}

小结：还是一维的dp，要考虑每个数用完全平方数与不用完全平方数之间哪个最优，且不大于该数的完全平方数都要试一遍。