推 wu10200512: 老哥 過年了別捲了 02/09 07:40
→ Apache: i**2<=n的i不應該這樣找== 02/09 10:58
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