Leetcode -279- Perfect square number
[Blog link]
A path to learning at 🐔
[B].
Given a positive integer n, find several perfect squares (e.g1.4.9.16,...). So that their sum is equal to n. You want to minimize the number of perfect squares that make up the sum. Given an integer n, return the minimum number of perfect squares that sum to n. A perfect square is an integer whose value equals the square of another integer; In other words, its value is equal to the product of an integer. For example,1,4,9 和 16These are perfect squares, and3 和 11It isn't. The sample1: Enter: n =12Output:3Explanation:12 = 4 + 4 + 4The sample2: Enter: n =13Output:2Explanation:13 = 4 + 9Tip:1 <= n <= 104Related Topics breadth of priority search mathematical dynamic programming 👍932 👎 0
Copy the code[答 案]
Leetcode topic link
[making address]
Code link
[Related topics]
Leetcode -322- Change
This site links
[introduction]
Idea 1: Exhaustive + DFS
- First determine the range of perfect squares (the largest perfect square cannot exceed n) to obtain all sets of squares
- The next step is to change to a knapsack problem like change to an item with the weight of the current array
- The cost of each item is 1, and the minimum cost of knapsack capacity N needs to be achieved. There are unlimited knapsacks
- So you can do DFS first
- This is definitely a TLE approach (use case stuck at 50)
public int numSquares(int n) {
// Corner case has been removed
int sum = (int) Math.sqrt(n);
int[] nums = new int[sum + 1];
// The positive ordinal group is guaranteed
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;
}
Copy the codeTime complexity O(n^\sqrt{n})
Idea 2: DFS + memorization
- It can be observed from the above recursive equation that the recursive equation is only related to n and min
- Specify map with n+ _ + min as key
- In fact, this one is also TLE, the use case is stuck at 50
Map<String, Integer> map = new HashMap<>();
public int numSquares(int n) {
// Corner case has been removed
int sum = (int) Math.sqrt(n);
int[] nums = new int[sum + 1];
// The positive ordinal group is guaranteed
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;
}
Copy the codeTime complexity can be understood simply as O(n^\ SQRT {n})
Idea three: the optimization of memory
-
By observing the above recursive equation, it is found that min has no effect on the result
-
Therefore, the storage of min can be cancelled to reduce the map access time
Map<Integer, Integer> map = new HashMap<>();
public int numSquares(int n) {
// Corner case has been removed
int sum = (int) Math.sqrt(n);
int[] nums = new int[sum + 1];
// The positive ordinal group is guaranteed
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;
}
Copy the codeTime complexity can be understood simply as O(n^\ SQRT {n})
Idea 4: Dynamic planning
- The above problems can undoubtedly be transformed into dynamic programming schemes
- According to the recursive equation, it can be found that the variable parameter has n and I parameters
- Define a dp[I] that uses the minimum number of digits that make up I dp[0] = 0 when I == 0
- Because there must be a perfect sum of squares of 1 =1 so dp[I] =1 when 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];
// The positive ordinal group is guaranteed
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];
}
Copy the codeTime complexity O(n n\ SQRT {n}n)*
Idea 5: Mathematical formulas
I’m not going to write the idea because I don’t understand it either
Answer key link