首页 > 代码库 > LeetCode 279. Perfect Squares
LeetCode 279. Perfect Squares
Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...
) which sum to n.
For example, given n = 12
, return 3
because 12 = 4 + 4 + 4
; given n = 13
, return 2
because 13 = 4 + 9
.
【题目分析】
一个数可以由一些完全平方数相加得到,例如1,4,9,16,...
给定一个数n,求出使得相加结果为n所需最少的完全平方数的个数。
【思路】
1. 递归
对于一个数,我们怎么求它的由哪些完全平方数相加得到的呢?
首先找到距离这个数最近的完全平方数m = x*x,我们从1~x中选择一个数,求出n中包含z个x*x,我们在递归求出n-z*x*x所包含的完全平方数。遍历1~x,返回其中最小的结果。
2. 动态规划
动态规划用 dp[i] 数组存储第 i 个数的完美平方数。递推式为:dp[i] = Math.min(dp[j] + dp[i-j], dp[i]),认为 i 的完全平方数是从和为 i 的两个完全平方数 dp[j] 和 dp[i-j]之和,然后从中取最小。
3. 改进后的动态规划
如图所示,红色部分表示平方数,所有的数都可以看做一个普通数加上一个完美平方数,那么递推式就变为了:dp[i + j * j] = Math.min(dp[i] + 1, dp[i + j * j])。
【java递归实现】
1 public class Solution { 2 public int numSquares(int n) { 3 int count = n; 4 int nearest = (int)Math.sqrt(n); 5 if(n == 0) return 0; 6 if(nearest*nearest == n) return 1; 7 for(int i = nearest; i >= 1; i--) { 8 int cur = 0, num = n, t = i*i; 9 while(num - t >= 0) { 10 num -= t; 11 cur++; 12 } 13 if(cur < count){ 14 count = Math.min(numSquares(num)+cur, count); 15 } 16 } 17 18 return count; 19 } 20 }
时间606ms
【java实现动态规划】
1 public class Solution { 2 /* 3 动态规划的思想来解决,递推公式dp[i] = Math.min(dp[j] + dp[i-j], dp[i]) 4 */ 5 public int numSquares(int n) { 6 int[] array = new int[n+1]; 7 Arrays.fill(array, Integer.MAX_VALUE); 8 array[1] = 1; 9 10 for(int i = 2; i <=n; i++) { 11 int sqr = (int)Math.sqrt(i); 12 if(sqr*sqr == i) array[i] = 1; 13 else{ 14 for(int j = 1; j <= i/2; j++) { 15 array[i] = Math.min(array[j]+array[i-j], array[i]); 16 } 17 } 18 } 19 return array[n]; 20 } 21 }
时间:1112ms
【java实现改进后的动态规划】
1 public class Solution { 2 /* 3 改进后动态规划,递推公式dp[i+j*j] = Math.min(dp[i]+1, dp[i+j*j]) 4 */ 5 public int numSquares(int n) { 6 int[] array = new int[n+1]; 7 Arrays.fill(array, Integer.MAX_VALUE); 8 9 for(int i = 1; i*i <= n; i++) { 10 array[i*i] = 1; 11 } 12 for(int i = 1; i <= n; i++) { 13 for(int j = 1; i+j*j <= n; j++) { 14 array[i+j*j] = Math.min(array[i]+1, array[i+j*j]); 15 } 16 } 17 return array[n]; 18 } 19 }
时间:60ms
LeetCode 279. Perfect Squares