etc mil osi res sans gin segment cnblogs
方法一: 动态规划
https://segmentfault.com/a/1190000003768736
https://siddontang.gitbooks.io/leetcode-solution/content/dynamic_programming/perfect_squares.html
复杂度
时间 O(N^2) 空间 O(N)
思路
如果一个数 x 可以表示为一个任意数 a 加上一个平方数 bxb,也就是 x=a+bxb,那么能组成这个数 x 最少的平方数个数,就是能组成 a 最少的平方数个数加上 1(因为 b*b 已经是平方数了)。
- public class Solution {
- /**
- * @param n a positive integer
- * @return an integer
- */
- public intnumSquares(int n) {
- // Write your code here
- int[] dp =new int[n + 1];
- // 将所有非平方数的结果置最大,保证之后比较的时候不被选中
- Arrays.fill(dp, Integer.MAX_VALUE);
- // 将所有平方数的结果置1
- for(inti = 0; i * i <= n; i++) {
- dp[i * i] = 1;
- }
- // 从小到大找任意数a
- for(inti = 0; i <= n; i++) {
- // 从小到大找平方数bxb
- for(intj = 1; i + j * j <= n; j++) {
- // 因为a+b*b可能本身就是平方数,所以我们要取两个中较小的dp[i + j * j] = Math.min(dp[i] + 1, dp[i + j * j]);
- }
- }
- return dp[n];
- }
- }
方法二:
数学 四平方和定理
https://www.cnblogs.com/grandyang/p/4800552.html
时间 O(N^2) 空间 O(N)
如果一个数 x 可以表示为一个任意数 a 加上一个平方数 bxb,也就是 x=a+bxb,那么能组成这个数 x 最少的平方数个数,就是能组成 a 最少的平方数个数加上 1(因为 b*b 已经是平方数了)。
Perfect Squares
来源: http://www.bubuko.com/infodetail-2087308.html