LeetCode : 279. Perfect Squares 数值平方和最小个数 我不是女神ヾ 2021-06-24 16:11 311阅读 0赞 **试题** Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, …) which sum to n. Example 1: Input: n = 12 Output: 3 Explanation: 12 = 4 + 4 + 4. Example 2: Input: n = 13 Output: 2 Explanation: 13 = 4 + 9. **代码** 用了个动归算法。比较容易想。其实还有贪心算法。可以把这一题视为金币求和。 class Solution { public int numSquares(int n) { int max = (int)Math.sqrt(n); int[] dp = new int[n+1]; for(int i=1; i<=n; i++){ dp[i] = i; for(int j=1; j<=max && j*j<=i; j++){ dp[i] = Math.min(dp[i], dp[i-j*j]+1); } } return dp[n]; } }
还没有评论,来说两句吧...