279.完全平方数

给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。
完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
：痕迹

1. class Solution {
2.     public int numSquares(int n) {
3.         // 从nums(完全平方数构成的数组)选和为n的组合
4.         // 1、4、9、16、25、36、49、64...
5.         int sqrt = (int)Math.sqrt(n);
6.         int[] nums = new int[sqrt];
7.         for(int i = 0; i < nums.length; i++){
8.             nums[i] = (i + 1) * (i + 1);
9.         }
10.         // 容量n
11.         // dp代表数量，
12.         // dp[j]的值是如何保证,当容量为j的时候，找到【数量最少】的【和为j】的
13.         int[] dp = new int[n + 1];
14.         int max = Integer.MAX_VALUE;
15.         for(int i = 1; i <= n; i++) dp[i] = max;
16.         /*
17.         for(int i = 1; i <= n; i++){
18.             for(int j = 0; j < nums.length; j++){
19.                 // 每次就决定加 / 不加 这个数。而这个数不是连续递增的，1.4.9.16.25.
20.                 // 那就说明，必定有一些数，不能由nums中的数相加的来（不是的，nums中还有1，所以必定能表示所有数字）
21.                
22.                 // 加不了当前的数
23.                 if(i < nums[j]) dp[i] = dp[i - 1];
24.                 // 加上当前这个nums[j]，则数量dp +1
25.                 else dp[i] = Math.min(dp[i], dp[i - nums[j]] + 1);
26.             }
27.         }
28.         */
29.         // dp[0] = 1;
30.         for(int i = 0; i < nums.length; i++){
31.             for(int j = nums[i]; j <= n; j++){
32.                 if(j == nums[i]) dp[j] = 1;
33.                 else dp[j] = Math.min(dp[j], dp[j - nums[i]] + 1);
34.             }
35.         }
36.         return dp[n];
37.     }
38. }

复制代码

感想：dp不知道先遍历容量还是数组的话，就都实行一下。

	i=0	i=1	i=2
0	0	0	0
1	1
2	2
3	3
4	4	1
5	5	2
6	6	3
7	7	4
8	8	2
9	9	3	1
10	10	4	2
11	11	5	3
12	12	3	4

 每个容量（上图中的行数据）取背面的最小值。对应代码：dp[j] = Math.min(dp[j], dp[j - nums] + 1);
：默写加深印象

1. public int numSquares(int n){
2.     // 需要自己构造数组
3.     int sqrt = (int)Math.sqrt(n);
4.     int[] nums = new int[sqrt];
5.     for(int i = 0; i < sqrt; i++) nums[i] = (i + 1) * (i + 1);
6.     //
7.     int[] dp = new int[n + 1];
8.     int max = Integer.MAX_VALUE;
9.     for(int i = 1; i <= n; i++) dp[i] = max;
10.     for(int i = 0; i < nums.length; i++){
11.         for(int j = nums[i]; j <= n; j++){
12.             if(j == nums[i]) dp[j] = 1;
13.             else dp[j] = Math.min(dp[j], dp[j - nums[i]] + 1);
14.         }
15.     }
16.     return dp[n];
17. }

复制代码

：改进

1. public int numSquares(int n){
2.     // 需要自己构造数组
3.     int sqrt = (int)Math.sqrt(n);
4.     int[] nums = new int[sqrt];
5.     for(int i = 0; i < sqrt; i++) nums[i] = (i + 1) * (i + 1);
6.     //
7.     int[] dp = new int[n + 1];
8.     int max = Integer.MAX_VALUE;
9.     // 这里要么从1开始遍历，要么从0开始，但还要把dp[0] = 0初始化。
10.     for(int i = 1; i <= n; i++) dp[i] = max;
11.     for(int i = 0; i < nums.length; i++){
12.         for(int j = nums[i]; j <= n; j++){
13.             dp[j] = Math.min(dp[j], dp[j - nums[i]] + 1);
14.         }
15.     }
16.     return dp[n];
17. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。