# 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]