Complete square
Title Description ： Given a positive integer n, Find some perfect squares （ such as 1, 4, 9, 16, ...） Make their sum equal to n. You need to minimize the number of complete squares that make up the sum .
Give you an integer n , Return and for n Of the complete square of Minimum quantity .
Complete square It's an integer , Its value is equal to the square of another integer ; let me put it another way , Its value is equal to the product of the self multiplication of an integer . for example ,1、4、9 and 16 They're all perfect squares , and 3 and 11 No .
Please refer to LeetCode Official website .
source ： Power button （LeetCode）
link ：https://leetcode-cn.com/probl...
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .
Solution 1 ： Dynamic programming
It is solved by dynamic programming , First , Initialize a dp The array is used to record the minimum number of power and cumulative number of each bit , Then initialize the value of each bit to the maximum value for subsequent comparison , Then the core logic is the following traversal process ：
- The first i The power sum of bits can be composed of i -> j j This step add j j The sum of the multiplier steps of , Then compare the smaller value of each judgment as the second i Number of bits .
explain ： Read the online analysis and solution process according to mathematical logic , The focus is on analysis , It's just , I don't quite understand , It turns out that only a few situations can be analyzed through mathematical analysis , Then judge according to these situations .
public class LeetCode_279 {
/**
* Dynamic programming
*
* @param n
* @return
*/
public static int numSquares(int n) {
// Record the minimum number of power and cumulative number of each bit
int[] dp = new int[n + 1];
for (int i = 1; i <= n; i++) {
// Initialize each number to the maximum value
dp[i] = Integer.MAX_VALUE;
}
// from 1 To traverse the
for (int i = 1; i <= n; i++) {
for (int j = 1; j * j <= i; j++) {
if (i >= j * j) {
// The logic here is No i The power sum of bits can be composed of i -> j * j This step add j * j The sum of the multiplier steps of , Then compare the smaller value of each judgment as the second i Number of bits
dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
}
}
}
return dp[n];
}
public static void main(String[] args) {
// Test case one , Expected output ： 3 （ from 4 + 4 + 4 obtain ）
System.out.println(numSquares(12));
// Test case 2 , Expected output ： 2 （ from 4 + 9 obtain ）
System.out.println(numSquares(13));
}
}
【 Daily message 】 Learning enriches one's knowledge , Knowledge improves one's ability , To make people create performance .
