Leetcode # 79. Perfect Squares
https://leetcode.com/problems/perfect-squares
Solution
問題所求的是合成數字 n 所需 perfect square 最小數量
故，此題
| dp[l] | := | l 個 perfect square 能合成出來的數 |
| = | [e + ps for e in dp[l – 1] for ps in pss] | |
| pss | := | [1, 4, 9, … , floor(n(1/2))2] |
若改成
| dp[l] | := | 合成數字 l 所需 perfect square 最小數量 |
| = | min([dp[l – ps] for ps in pss if l >= ps]) + 1 | |
| dp[0] | := | 0 |
則 time complexity 能再縮減為 O(n * (n(1/2)))
Time Complexity: O((n2) * (n(1/2)))
Space Complexity: O(n)
(The input and output generally do not count towards the space complexity.)
class Solution:
def numSquares(self, n: int) -> int:
pss = dp = [i ** 2 for i in range(1, int(n ** (1/2) + 1.5))]
if n in dp: return 1
for l in range(2, n + 1):
next_dp = []
for e in dp:
for ps in pss:
_e = e + ps
if _e < n:
next_dp.append(_e)
elif _e == n:
return l
dp = next_dp
↓
Time Complexity: O((n2) * (n(1/2)))
Space Complexity: O(n)
(The input and output generally do not count towards the space complexity.)
class Solution:
def numSquares(self, n: int) -> int:
pss = [i ** 2 for i in range(1, int(n ** (1/2) + 1.5))]
dp = [0] + [inf for l in range(n)]
for l in range(1, n + 1):
dp[l] = min([dp[l - ps] for ps in pss if l >= ps]) + 1
return dp[-1]
Last Updated on 2023/08/16 by A1go
