Perfect Squares
Problem
Given an integer n, return the least number of perfect-square numbers (1, 4, 9, 16, …) that sum to n.
n = 123def num_squares(n):
dp = [0] + [float('inf')] * n
for i in range(1, n + 1):
k = 1
while k * k <= i:
dp[i] = min(dp[i], dp[i - k * k] + 1)
k += 1
return dp[n]function numSquares(n) {
const dp = new Array(n + 1).fill(Infinity);
dp[0] = 0;
for (let i = 1; i <= n; i++) {
for (let k = 1; k * k <= i; k++) {
dp[i] = Math.min(dp[i], dp[i - k * k] + 1);
}
}
return dp[n];
}class Solution {
public int numSquares(int n) {
int[] dp = new int[n + 1];
Arrays.fill(dp, Integer.MAX_VALUE);
dp[0] = 0;
for (int i = 1; i <= n; i++)
for (int k = 1; k * k <= i; k++)
dp[i] = Math.min(dp[i], dp[i - k * k] + 1);
return dp[n];
}
}int numSquares(int n) {
vector<int> dp(n + 1, INT_MAX);
dp[0] = 0;
for (int i = 1; i <= n; i++)
for (int k = 1; k * k <= i; k++)
dp[i] = min(dp[i], dp[i - k * k] + 1);
return dp[n];
}Explanation
We want the fewest perfect squares (1, 4, 9, 16, ...) that add up to n. The idea is to solve every smaller number first, then reuse those answers — that is what makes this dynamic programming.
We define dp[i] as the minimum number of squares that sum to i. We know dp[0] = 0 (zero needs nothing) and set everything else to infinity to start.
To fill dp[i], we try subtracting each square k*k that is not bigger than i. Using that square costs one piece, plus the best way to make the remainder, which we already computed: dp[i - k*k] + 1. We keep the smallest over all valid k.
Example: n = 12. For dp[12] we can subtract 4 (i.e. 2*2) to land on 8; since dp[8] = 2, that gives 3. That matches 12 = 4 + 4 + 4, so the answer is 3.
The final answer is dp[n]. Each number tries about √n squares, so the total work is O(n·√n).