sosodemonai https://blog.hatena.ne.jp/sosodemonai/ Neunomizuの日記 https://propyon.hateblo.jp/ leetcode tags: leetcode 問題 Explore Problems アイデア ｢正整数 $n$ が与えられた時， $n$ を平方数の和だけで表した時に，使うのに必要な最小の平方数の数を返せ｣という問題です． よくわからない… 解法 動的計画法でした(完) 配列を dp[i番目までの数] = iを平方数の和で表したときの最小の平方数の個数 として，後は各平方数ごとに配列を更新する． 計算量 時間計算量 $O(n \sqrt{n})$ 空間計算量 $O(n)$ Python class Solution: def numSquares(self, n: int) -> int: dp = [fl… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fpropyon.hateblo.jp%2Fentry%2F2020%2F05%2F14%2F230109" title="# LeetCode Medium 279. Perfect Squares - Neunomizuの日記" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2020-05-14 23:01:09 rich https://propyon.hateblo.jp/entry/2020/05/14/230109 1.0 100%