Perfect Squares
Given an integer n, return the least number of perfect square numbers (forQuestion and saidQuestion and can be expressed as the square of an integer) that sum to n.
Constraints:
- 1 <= n <= 12,000
Examples:
Input: 12
Output: 3
Explanation: Explanation: 4 + 4 + 4 = 12
Solutions
Dynamic Programming
We create a dynamic programming array dp where dp[i] represents the least number of perfect squares that sum to i. We initialize dp with infinity and set dp[0] to 0. Then we iterate over all numbers from 1 to n. For each number i, we check all perfect squares j * j that are less than or equal to i. We update dp[i] with the minimum of its current value and dp[i - j * j] + 1. Finally, we return dp[n].
int numSquares(int n) {
vector<int> dp(n + 1, INT_MAX);
dp[0] = 0;
for (int i = 1;
i <= n;
i++) {
int j = 1;
while (j * j <= i) {
dp[i] = min(dp[i], dp[i - j * j] + 1);
j++;
}
}
return dp[n];
}Follow-up:
What if we are given a target sum and a list of perfect squares, and we need to find the least number of perfect squares that sum to the target?
