279. 完全平方数
题目描述
给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。
示例 1:
输入: n = 12 输出: 3 解释: 12 = 4 + 4 + 4.
示例 2:
输入: n = 13 输出: 2 解释: 13 = 4 + 9.
思路一：暴力 dfs （时间超时）
先给n开平方，确定上界，假定 根号n等于k
递归，从1-k中选出多个值，每个值可选可不选，而且还能重复选，记录选中的次数
当前和如果刚好等于n, 则更新cnt
1 class Solution { 2 public int numSquares(int n) { 3 if(n <= 0){ 4 return 0; 5 } 6 7 // 先给n开平方，确定上界，假定 根号n等于k 8 int sqrt = (int)Math.sqrt(n); 9 traceBack(n, 0, sqrt, 0); 10 return cnt; 11 } 12 13 public int cnt = 1 << 30; 14 15 // 递归，从1-k中选出多个值，每个值可选可不选，而且还能重复选，记录选中的次数 16 public void traceBack(int n, int nowSum, int index, int count){ 17 // 越界，或者如果大于n, 直接返回 18 if(index <= 0 || n < nowSum){ 19 return; 20 } 21 // 边界如果刚好等于n, 则更新cnt 22 if(n == nowSum){ 23 cnt = Math.min(cnt, count); 24 } 25 26 // 对于每个数可选也不可选 27 // 选 28 if(nowSum + index * index <= n){ 29 traceBack(n, nowSum + index * index, index, count + 1); 30 } 31 32 // 不选 33 traceBack(n, nowSum, index-1, count); 34 } 35 }
通过了287个测试用例，然后就超时了
复杂度分析：
时间复杂度：对小于√n 的所有数都进行枚举，而且每个数还不止枚举一遍，所以这个复杂度就不太好算了，我觉得是 2n√n
空间复杂度：递归栈的深度，我觉得是√n
思路二：动态规划
dp[i]表示组成i的最少完全平方的个数
i 和 (i - j * j)的最终结果就相差一个完全平方数j*j, 所以dp[i] 和 dp[i-j*j]就相差1
dp[i] = Math.min(dp[i], dp[i - j*j] + 1); dp[0] = 0;
边界值dp[i] = i, 因为组成i的最少完全平方的个数最大为i, 即全是由1组成的
1 class Solution { 2 public int numSquares(int n) { 3 if(n <= 0){ 4 return 0; 5 } 6 7 int[] dp = new int[n+1]; 8 dp[0] = 0; 9 for(int i = 1; i <= n; i++){ 10 dp[i] = i; 11 for(int j = 0; i - j*j >= 0; j++){ 12 dp[i] = Math.min(dp[i], dp[i - j*j] + 1); 13 } 14 } 15 return dp[n]; 16 } 17 }
leetcode 执行用时：42 ms > 64.61%, 内存消耗：37.5 MB > 94.62%
复杂度分析：
时间复杂度：O(n√n). 两个for循环，外层循环的循环次数是n, 内层循环的循环次数最大为√n, 所以总的时间复杂度为O(n√n)
空间复杂度：O(n). 需要一个大小为 (n+1)的数组，所以空间复杂度为O(n)