Re: [閒聊] 每日LeetCode已回收
看板Marginalman作者JerryChungYC (JerryChung)時間1年前 (2024/02/09 05:36)推噓1(1推 0噓 1→)留言2則, 2人參與討論串662/719 (看更多)
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的 全列出來嗎
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 61.224.85.206 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1707428184.A.E8C.html
推
02/09 07:40,
1年前
, 1F
02/09 07:40, 1F
→
02/09 10:58,
1年前
, 2F
02/09 10:58, 2F
討論串 (同標題文章)