青岛天河小学网站建设,上海网站设计成功柚v米科技,四川建设网证书查询平台官网,全新wordpress主题题意理解#xff1a; 给你一个整数 n #xff0c;返回 和为 n 的完全平方数的最少数量 。 完全平方数 是一个整数#xff0c;其值等于另一个整数的平方#xff1b;换句话说#xff0c;其值等于一个整数自乘的积。例如#xff0c;1、4、9 和 16 都是完全平方数#xff0c… 题意理解 给你一个整数 n 返回 和为 n 的完全平方数的最少数量 。 完全平方数 是一个整数其值等于另一个整数的平方换句话说其值等于一个整数自乘的积。例如1、4、9 和 16 都是完全平方数而 3 和 11 不是。 从题目中可以理解 元素是平方数即149... 元素可以使用无数次。 而整数n表示要使用平方数凑数来的目标。 则该问题是一个完全背包问题。 又因为这里求凑出target的最少完全平方数所以这里不是一个纯背包问题。 又因为144 和414都是用了三个平方数所以顺序是无关的排列数和组合数都可以解决这个问题即双for循环可以颠倒。 此外如何遍历完全平方数呢 我们可以采用for(int i0;i;i) 完全平方数i×i的方式来遍历。 因为要使用i×i来凑n所以i一定 解题思路 此题是一道完全背包问题但是是非纯背包问题。因为这里求的是最少用几个元素而不是最大价值。 这里的元素是i^2,其中i是[1,]的整数 目标值是targetn 元素可以无数次取用。 1.解题
public int numSquares(int n) {int dp[]new int[n1];Arrays.fill(dp,Integer.MAX_VALUE);dp[0]0;for(int i1;iMath.sqrt(n);i){//遍历元素for(int j1;jn;j){if(Math.pow(i,2)jInteger.compare(Integer.MAX_VALUE,dp[j-(int)Math.pow(i,2)])!0){dp[j]Math.min(dp[j],dp[j-(int)Math.pow(i,2)]1);}}}return Integer.compare(Integer.MAX_VALUE,dp[n])!0?dp[n]:-1;}
2.分析 时间复杂度O(n^2) 空间复杂度O(n)
