Dare2Solve
Given a positive integer n
, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n
.
To solve this problem, we can use a dynamic programming approach. The idea is to build up a solution for n
by using solutions for smaller numbers. Specifically, for each number num
from 1
to n
, we can find the minimum number of perfect squares that sum to num
by considering all perfect squares less than or equal to num
.
Memoization Initialization:
memo
of size 10001
and initialize all values to -1
. This array will store the minimum number of perfect squares that sum to each index.Recursive Function:
dp(num, memo)
that returns the minimum number of perfect squares that sum to num
.num < 0
, return a large number (10000
) because it is an invalid case.num == 0
, return 0
because no squares are needed to sum to zero.memo[num] != -1
, return the memoized result to avoid redundant calculations.i
from 1
to 100
, compute the minimum number of squares needed for num - i*i
and update mini
.num
.Main Function:
dp(n, memo)
to get the result.O(n * sqrt(n))
n
states and for each state, we loop up to sqrt(n)
.O(n)
O(n)
space.class Solution {
public:
int numSquares(int n) {
vector<int> memo(10001, -1);
return dp(n, memo);
}
private:
int dp(int num, vector<int>& memo) {
if (num < 0) return 10000;
if (num == 0) return 0;
if (memo[num] != -1) return memo[num];
int mini = 100000;
for (int i = 1; i <= 100; i++) {
mini = min(mini, 1 + dp(num - i * i, memo));
}
return memo[num] = mini;
}
};
class Solution:
def numSquares(self, n: int) -> int:
if n <= 0:
return 0
queue = deque([n])
visited = set([n])
level = 0
while queue:
level += 1
size = len(queue)
for _ in range(size):
current = queue.popleft()
for i in range(1, int(current**0.5) + 1):
remainder = current - i*i
if remainder == 0:
return level
if remainder not in visited:
visited.add(remainder)
queue.append(remainder)
return level
class Solution {
public int numSquares(int n) {
int[] memo = new int[10001];
Arrays.fill(memo, -1);
return dp(n, memo);
}
private int dp(int num, int[] memo) {
if (num < 0) return 10000;
if (num == 0) return 0;
if (memo[num] != -1) return memo[num];
int mini = 100000;
for (int i = 1; i <= 100; i++) {
mini = Math.min(mini, 1 + dp(num - i * i, memo));
}
memo[num] = mini;
return mini;
}
}
var numSquares = function (n) {
let memo = Array(10001).fill(-1);
return dp(n, memo);
};
function dp(num, memo) {
if (num < 0) return 10000;
if (num === 0) return 0;
if (memo[num] !== -1) return memo[num];
let mini = 100000;
for (let i = 1; i <= 100; i++) {
mini = Math.min(mini, 1 + dp(num - i * i, memo));
}
return memo[num] = mini;
}