LeetCode: Perfect Squares (Dynamic Programming)
https://leetcode.com/problems/perfect-squares/, problem statement:
Given a positive integer n, find the least number of perfect square numbers (for example,
1, 4, 9, 16, ...) which sum to n.
For example, given n =
12, return 3 because 12 = 4 + 4 + 4; given n = 13, return 2 because 13 = 4 + 9.
Assume you know the solution for all values from 1..N-1. Then when evaluating the solution for N, subtract from N all the squares up to N and see which ones from the previous solutions (DP), plus one, gives you the least number of solutions. At the end the solution will be stored in the position n. Complexity is somewhere in the neighborhood of N*Sqrt(N) and N*Log(N). Code's below, cheers, Marcelo.
public class Solution
{
public int NumSquares(int n)
{
int[] best = new int[n + 1];
best[0] = 0;
for (int i = 1; i <= n; i++)
{
best[i] = Int32.MaxValue;
for (int j = 1; j * j <= i; j++)
{
if (1 + best[i - j * j] < best[i]) best[i] = 1 + best[i - j * j];
}
}
return best[n];
}
}
"Perfection is achieved, not when there is nothing more to add, but when there is nothing left to take away."
ReplyDelete-- Antoine de Saint-Exupery
Your solution is perfect! This problem is a variation of a classical change making problem and your solution deserves to be its classical solution :)
FYI, my solution in C++:
class Solution {
public:
int numSquares(int n) {
vector min_summand_count(n+1, numeric_limits::max());
min_summand_count[0] = 0;
for (int num = 1; num <= n; ++num) {
for (int i = 1; i * i <= num; ++i) {
min_summand_count[num] = min(min_summand_count[num], 1 + min_summand_count[num-i*i]);
}
}
return min_summand_count[n];
}
};