1.6 KiB
1.6 KiB
layout, title, last_solved, category, leetcode_url, status
| layout | title | last_solved | category | leetcode_url | status |
|---|---|---|---|---|---|
| page | Perfect Squares | 2020-06-28 | dp [bottom up] | https://leetcode.com/problems/perfect-squares/ | Semi-Solved |
Problem
Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.
Example 1:
Input: n = 12
Output: 3
Explanation: 12 = 4 + 4 + 4.
Example 2:
Input: n = 13
Output: 2
Explanation: 13 = 4 + 9.
Solution
This is suppose to be similar to the coin change problem somehow.
1 -> 1 (1)
2 -> 2 (1+1)
3 -> 3 (1+1+1)
4 -> 1 (4)
5 -> 2 (4+1)
6 -> 3 (4+1+1)
7 -> 4 4+1+1+1
8 -> 2 4+4
f(1) = 1
f(2) = f(1) + f(1) = 1+1=2
f(7) = f(4) + f(3) = 1+3=4
f(8) = f(4) + f(4) = 1+1=2
f(12) = f(8) + f(4) = 2+1=3
identify subproblems?
https://leetcode.com/problems/perfect-squares/discuss/696436/Python-Simple-DP-Solution
n=7
square_sums = [0,1,4]
dp = [0, inf, inf, inf, inf, inf, inf, inf]
0 1 2 3 4 5 6 7
dp = [0, 1, 2, 3, 1, 2, 3, 4]
dp = [0, 1, inf, inf, 1, inf, inf, inf]
i: 1->n
iter all squares
min( dp[i], dp[i-square] )
{% highlight python %}
def numSquares(self, n: int) -> int: ## RC ## ## APPROACH : DP ##
## TIME COMPLEXITY : O(N^2) ##
## SPACE COMPLEXITY : O(N) ##
if( n < 3) : return n
square_nums = [i**2 for i in range(0, int(math.sqrt(n))+1)]
dp = [float('inf')] * (n+1)
dp[0] = 0
for i in range(1, n+1):
for square in square_nums:
if(i < square): break
dp[i] = min(dp[i], dp[i-square] + 1) # +1 is for that square we are substracting.
return dp[-1]
{% endhighlight %}