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的 全列出來嗎
這題最快都是用數學理論解
three square theory
four square theory
去看一下
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.83.32.121 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1707442707.A.984.html
※ 編輯: JIWP (111.83.32.121 臺灣), 02/09/2024 09:39:22
推
02/09 09:49,
1年前
, 1F
02/09 09:49, 1F
→
02/09 09:50,
1年前
, 2F
02/09 09:50, 2F
討論串 (同標題文章)
完整討論串 (本文為第 663 之 719 篇)：