Re: [閒聊] 每日LeetCode
※ 引述《JerryChungYC (JerryChung)》之銘言：
: https://leetcode.com/problems/perfect-squares
: ※ 引述《DJYOSHITAKA (franchouchouISBEST)》之銘言：
: : 279. Perfect Squares
: : n必定能由一組可重複的正整數的平方和所組成
: : 找出最少個數的數組能透過平方和組出n
: : 回傳個數
: Python3 code:
: ----------------------------------------------------
: class Solution:
: def numSquares(self, n: int) -> int:
: sqs = []
: dp = [(n + 1) for _ in range(n + 1)]
: dp[0] = 0
: for i in range(1, n + 1):
: if (i ** 0.5) == int(i ** 0.5):
: sqs.append(i)
: dp[i] = 1
: continue
: cost = n + 1
: for c in sqs:
: if i >= c:
: cost = min(dp[i - c] + 1, cost)
: if cost == 2:
: break
: dp[i] = cost
: return dp[n] if dp[n] != n + 1 else -1
: -----------------------------------------------------
: 不會動態規劃 求教 :(
: 話說這解1776ms 怎麼Python3最快有46ms的 全列出來嗎
我的好慢 155ms==
class Solution:
dp = {}
def numSquares(self, n: int) -> int:
if res := self.dp.get(n):
return res
res = n
for i in range(int(n**0.5), 1, -1):
res = min(res, self.numSquares(n - i ** 2) + 1)
if res == 1:
break
self.dp[n] = res
return res
這個要改iteration有點麻煩
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 39.10.26.67 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1707464286.A.3FE.html
→
02/09 15:39,
2月前
, 1F
02/09 15:39, 1F
討論串 (同標題文章)