98 lines
1.6 KiB
Markdown
98 lines
1.6 KiB
Markdown
---
|
|
layout: page
|
|
title: Perfect Squares
|
|
last_solved: 2020-06-28
|
|
category: dp [bottom up]
|
|
leetcode_url: https://leetcode.com/problems/perfect-squares/
|
|
status: 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 %}
|
|
|
|
|
|
![image1]() |