leetcode-279-完全平方数

[题目描述]

  1. 给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。 
  3.  给你一个整数 n ，返回和为 n 的完全平方数的 最少数量 。 
  5.  完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
  10.  示例 1： 
  13. 输入：n = 12
  14. 输出：3 
  15. 解释：12 = 4 + 4 + 4 
  17.  示例 2： 
  20. 输入：n = 13
  21. 输出：2
  22. 解释：13 = 4 + 9 
  25.  提示： 
  28.  1 <= n <= 104 
  30.  Related Topics 广度优先搜索 数学 动态规划 
  31.  👍 932 👎 0

[题目链接]

leetcode题目链接

[github地址]

代码链接

[相关题目]

leetcode-322-零钱兑换

本站链接

[思路介绍]

思路一：穷举+dfs

  • 首先确定完全平方数范围（最大的完全平方数不能超过n）得到所有平方数数组
  • 接下来就转变成了类似（零钱兑换）的背包问题 题意转换为 有当前数组重量的物品
  • 每一件物品成本为1，需要达成背包容量n的最小成本，背包数量无限个
  • 所以可以先用dfs做
  • 毫无疑问这是一个会TLE的做法(用例卡在了50)
  1. public int numSquares(int n) {
  2.             //corner case 已经被题目限制去掉了
  3.             int sum = (int) Math.sqrt(n);
  4.             int[] nums = new int[sum + 1];
  5.             //同时保证了正序数组
  6.             for (int i = 0; i <= sum; i++) {
  7.                 nums[i] = i * i;
  8.             }
  9.             int min = Integer.MAX_VALUE;
  10.             return dfs(nums, n, min);
  11.         }
  13.         public int dfs(int[] nums, int n, int min) {
  14.             if (n < 0) {
  15.                 return -1;
  16.             }
  17.             if (n == 0) {
  18.                 return 0;
  19.             }
  20.             for (int i = 1; i < nums.length; i++) {
  21.                 int res = dfs(nums, n - nums[i],min);
  22.                 if (res >= 0 && res < min) {
  23.                     min = res + 1;
  24.                 }
  25.             }
  26.             return min == Integer.MAX_VALUE? -1 : min;
  27.         }

时间复杂度O(nleetcode-279-完全平方数 - 图1)

思路二：dfs+记忆化

  • 根据上述递归方程可以观察到递归方程只与n和min有关
  • 声明map，n+ “_” + min作为key
  • 其实这个也TLE了，用例卡在50
  1. Map<String, Integer> map = new HashMap<>();
  2.         public int numSquares(int n) {
  3.             //corner case 已经被题目限制去掉了
  4.             int sum = (int) Math.sqrt(n);
  5.             int[] nums = new int[sum + 1];
  6.             //同时保证了正序数组
  7.             for (int i = 0; i <= sum; i++) {
  8.                 nums[i] = i * i;
  9.             }
  10.             int min = Integer.MAX_VALUE;
  11.             return dfs(nums, n, min);
  12.         }
  13.         public int dfs(int[] nums, int n, int min) {
  14.             String key = min + "_" + n;
  15.             if (map.containsKey(key)){
  16.                 return map.get(key);
  17.             }
  18.             int temp = min;
  19.             if (n < 0) {
  20.                 return -1;
  21.             }
  22.             if (n == 0) {
  23.                 return 0;
  24.             }
  25.             for (int i = 1; i < nums.length; i++) {
  26.                 int res = dfs(nums, n - nums[i],min);
  27.                 if (res >= 0 && res < min) {
  28.                     min = res + 1;
  29.                 }
  30.             }
  32.             min =  min == Integer.MAX_VALUE? -1 : min;
  33.             map.put(temp + "_" + n,min);
  34.             return min;
  35.         }

时间复杂度可以简单理解时间复杂度O(nleetcode-279-完全平方数 - 图2)

思路三：记忆化的优化

  • 观察上述递归方程发现min并未对结果造成影响

  • 所以可以取消min的存储减少了map存取时间

  1. Map<Integer, Integer> map = new HashMap<>();
  2.         public int numSquares(int n) {
  3.             //corner case 已经被题目限制去掉了
  4.             int sum = (int) Math.sqrt(n);
  5.             int[] nums = new int[sum + 1];
  6.             //同时保证了正序数组
  7.             for (int i = 0; i <= sum; i++) {
  8.                 nums[i] = i * i;
  9.             }
  10.             int min = Integer.MAX_VALUE;
  11.             return dfs(nums, n, min);
  12.         }
  13.         public int dfs(int[] nums, int n, int min) {
  14.             if (map.containsKey(n)){
  15.                 return map.get(n);
  16.             }
  18.             if (n < 0) {
  19.                 return -1;
  20.             }
  21.             if (n == 0) {
  22.                 return 0;
  23.             }
  24.             for (int i = 1; i < nums.length; i++) {
  25.                 int res = dfs(nums, n - nums[i],min);
  26.                 if (res >= 0 && res < min) {
  27.                     min = res + 1;
  28.                 }
  29.             }
  31.             min =  min == Integer.MAX_VALUE? -1 : min;
  32.             map.put(n,min);
  33.             return min;
  34.         }

时间复杂度可以简单理解时间复杂度O(nleetcode-279-完全平方数 - 图3)

思路四：动态规划

  • 上述问题毫无疑问可以改造为动态规划的方案
  • 根据递归方程可以发现可变参数有n和i两个参数
  • 定义一个dp[i] 表示使用组成i的最小数字数量当i == 0 的时候 dp[0] = 0
  • 因为一定存在1 的完全平方和=1 所以当i == 1 的时候 dp[i] = 1
  • dp[i] = Math.min(dp[i-nums[0->nums.length-1]])
  1. public int numSquares(int n) {
  2.             int sum = (int) Math.sqrt(n);
  3.             int[] nums = new int[sum + 1];
  4.             //同时保证了正序数组
  5.             for (int i = 0; i <= sum; i++) {
  6.                 nums[i] = i * i;
  7.             }
  8.             int[] dp = new int[n + 1];
  9.             dp[1] = 1;
  10.             for (int i = 1; i <= n; i++) {
  11.                 int min = Integer.MAX_VALUE;
  12.                 for (int j = 1; j < nums.length && i >= nums[j]; j++) {
  13.                     min = Math.min(dp[i - nums[j]], min);
  14.                 }
  15.                 min += 1;
  16.                 dp[i] = min;
  17.             }
  18.             return dp[n];
  19.         }

**时间复杂度O(nleetcode-279-完全平方数 - 图4)

思路五：数学公式

这个我就不写理解思路了因为我也没看懂

题解链接