Neunomizuの日記

俺だけが俺だけじゃない

# LeetCode Medium 279. Perfect Squares

tags: leetcode

問題

イデア

「正整数 $n$ が与えられた時, $n$ を平方数の和だけで表した時に,使うのに必要な最小の平方数の数を返せ」という問題です.

よくわからない…

解法

動的計画法でした(完)

配列を

dp[i番目までの数] = iを平方数の和で表したときの最小の平方数の個数

として,後は各平方数ごとに配列を更新する.

計算量

  • 時間計算量
    • $O(n \sqrt{n})$
  • 空間計算量
    • $O(n)$

Python

class Solution:
    def numSquares(self, n: int) -> int:
        dp = [float('inf')] * (n + 1)
        dp[0] = 0
        for i in range(1, int(math.sqrt(n)) + 1):
            square_num = i * i
            for j in range(square_num, len(dp)):
                dp[j] = min(dp[j], 1 + dp[j - square_num])
        return dp[n]