leetcode-279-完全平方数

[博客链接]

[题目描述]

给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。 

 给你一个整数 n ，返回和为 n 的完全平方数的 最少数量 。 

 完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。




 示例 1： 


输入：n = 12
输出：3 
解释：12 = 4 + 4 + 4 

 示例 2： 


输入：n = 13
输出：2
解释：13 = 4 + 9 


 提示： 


 1 <= n <= 104 

 Related Topics 广度优先搜索 数学 动态规划 
 ? 932 ? 0
复制代码

[题目链接]

leetcode题目链接

[github地址]

代码链接

[相关题目]

leetcode-322-零钱兑换

本站链接

[思路介绍]

思路一：穷举+dfs

首先确定完全平方数范围（最大的完全平方数不能超过n）得到所有平方数数组
接下来就转变成了类似（零钱兑换）的背包问题题意转换为有当前数组重量的物品
每一件物品成本为1，需要达成背包容量n的最小成本，背包数量无限个
所以可以先用dfs做
毫无疑问这是一个会TLE的做法(用例卡在了50)

public int numSquares(int n) {
            //corner case 已经被题目限制去掉了
            int sum = (int) Math.sqrt(n);
            int[] nums = new int[sum + 1];
            //同时保证了正序数组
            for (int i = 0; i <= sum; i++) {
                nums[i] = i * i;
            }
            int min = Integer.MAX_VALUE;
            return dfs(nums, n, min);
        }

        public int dfs(int[] nums, int n, int min) {
            if (n < 0) {
                return -1;
            }
            if (n == 0) {
                return 0;
            }
            for (int i = 1; i < nums.length; i++) {
                int res = dfs(nums, n - nums[i],min);
                if (res >= 0 && res < min) {
                    min = res + 1;
                }
            }
            return min == Integer.MAX_VALUE? -1 : min;
        }
复制代码

时间复杂度O(n $^\sqrt{n}$ )

思路二：dfs+记忆化

根据上述递归方程可以观察到递归方程只与n和min有关
声明map，n+ “_” + min作为key
其实这个也TLE了，用例卡在50

Map<String, Integer> map = new HashMap<>();
        public int numSquares(int n) {
            //corner case 已经被题目限制去掉了
            int sum = (int) Math.sqrt(n);
            int[] nums = new int[sum + 1];
            //同时保证了正序数组
            for (int i = 0; i <= sum; i++) {
                nums[i] = i * i;
            }
            int min = Integer.MAX_VALUE;
            return dfs(nums, n, min);
        }
        public int dfs(int[] nums, int n, int min) {
            String key = min + "_" + n;
            if (map.containsKey(key)){
                return map.get(key);
            }
            int temp = min;
            if (n < 0) {
                return -1;
            }
            if (n == 0) {
                return 0;
            }
            for (int i = 1; i < nums.length; i++) {
                int res = dfs(nums, n - nums[i],min);
                if (res >= 0 && res < min) {
                    min = res + 1;
                }
            }

            min =  min == Integer.MAX_VALUE? -1 : min;
            map.put(temp + "_" + n,min);
            return min;
        }
复制代码

时间复杂度可以简单理解时间复杂度O(n $^\sqrt{n}$ )

思路三：记忆化的优化

观察上述递归方程发现min并未对结果造成影响
所以可以取消min的存储减少了map存取时间

Map<Integer, Integer> map = new HashMap<>();
        public int numSquares(int n) {
            //corner case 已经被题目限制去掉了
            int sum = (int) Math.sqrt(n);
            int[] nums = new int[sum + 1];
            //同时保证了正序数组
            for (int i = 0; i <= sum; i++) {
                nums[i] = i * i;
            }
            int min = Integer.MAX_VALUE;
            return dfs(nums, n, min);
        }
        public int dfs(int[] nums, int n, int min) {
            if (map.containsKey(n)){
                return map.get(n);
            }

            if (n < 0) {
                return -1;
            }
            if (n == 0) {
                return 0;
            }
            for (int i = 1; i < nums.length; i++) {
                int res = dfs(nums, n - nums[i],min);
                if (res >= 0 && res < min) {
                    min = res + 1;
                }
            }

            min =  min == Integer.MAX_VALUE? -1 : min;
            map.put(n,min);
            return min;
        }
复制代码

时间复杂度可以简单理解时间复杂度O(n $^\sqrt{n}$ )

思路四：动态规划

上述问题毫无疑问可以改造为动态规划的方案
根据递归方程可以发现可变参数有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]])

public int numSquares(int n) {
            int sum = (int) Math.sqrt(n);
            int[] nums = new int[sum + 1];
            //同时保证了正序数组
            for (int i = 0; i <= sum; i++) {
                nums[i] = i * i;
            }
            int[] dp = new int[n + 1];
            dp[1] = 1;
            for (int i = 1; i <= n; i++) {
                int min = Integer.MAX_VALUE;
                for (int j = 1; j < nums.length && i >= nums[j]; j++) {
                    min = Math.min(dp[i - nums[j]], min);
                }
                min += 1;
                dp[i] = min;
            }
            return dp[n];
        }
复制代码