279. Perfect Squares【Leetcode】の解説（っていうか記憶に強く残したいが故の自分用のメモ）です。
言語はpython3です。
279. Perfect Squares【Leetcode】の問題
Given an integer n, return the least number of perfect square numbers that sum to n.
A perfect square is an integer that is the square of an integer; in other words, it is the product of some integer with itself. For example, 1, 4, 9, and 16 are perfect squares while 3 and 11 are not.
訳：
整数 n が与えられたとき、和が n になる完全平方数の最小個数を返せ。
完全平方とは、ある整数の2乗である整数のことで、言い換えれば、ある整数とそれ自身との積である。例えば、1, 4, 9, 16は完全平方であるが、3と11は完全平方でない。
Example 1:
Input: n = 12
Output: 3
Explanation: 12 = 4 + 4 + 4.
Example 2:
Input: n = 13
Output: 2
Explanation: 13 = 4 + 9.
スポンサーリンク
279. Perfect Squares【Leetcode】の回答
回答は以下の通りです。
|
1 2 3 4 5 6 7 8 9 10 11 12 |
class Solution: def numSquares(self, n: int) -> int: square_num = [i**2 for i in range(0,int(math.sqrt(n))+1)] dp = [float('inf')] * (n+1) dp[0] = 0 for i in range(n+1): for num in square_num: if i < num: break dp[i] = min(dp[i],1+dp[i-num]) return dp[-1] |
スポンサーリンク
279. Perfect Squares【Leetcode】の解説
みた感じでもうなんとなくDP（Dynamic Programming）臭がしてきます。
返すべき値は最小個数です。その中身がどうであるかは問いません。
DPというのは簡単にいうと処理の中で何度も同じ計算をするのではなく、記録しておいたものを再利用しようぜ、というアルゴリズム手法です。
解法としてExample 1:を例に取ると、まず0からn＝12までの箱を用意します。それぞれ、その値を実現するための最小個数を記録していきます。
後々最小値で更新していきたいので、初期値として無限大(float(‘inf’))を入れておきます。
dp = [float(‘inf’)] * (n+1)
0から12までのインデックスを用意したいので、n+1としています。
これら各々の箱のインデックスの数に到達するまでの完全平方数の最小個数を記録していきます。
例えば0を実現するための完全平方数の最小個数は0ですがm
1なら1、2なら2（1+1=2）、3なら3(1+1+1=3）、4なら1（2の二乗）です。
｜0｜1｜2｜3｜4｜5｜6｜7｜8｜9｜10｜11｜12｜
｜0｜1｜2｜3｜1｜2｜ ｜ ｜ ｜ ｜ ｜ ｜ ｜
これらをどう埋めていくかというと12の平方根以下の整数で一つずつ検証していきます。それ以上の整数はとり得ないからです。
12の平方根は3.4641016151377544なので整数だけ取ると、3となり、square_numとして、3までの整数2乗リストを作成します。
square_num = [0,1,4,9]
もし整数がインデックスよりも大きければ、無視しますが、小さければより最小の個数を入れられるようにします。
そして極め付けはこれ。
dp[i] = min(dp[i], 1+dp[i-num]) *iはインデックス、numはsquare_numから取り出した時の値
ここがdpの問題として味噌です。
こうすることにより、例えばインデックスが5の場合、
dp[5] = min(dp[5], 1+dp[5-num])となります。
numはsquare_numから取り出した時の値ですが、square_num には [0,1,2,3]が存在しているので、各々の場合をループにより常に最小個数で更新されることになります。
1+dp[5-num]の+1の部分についてはnumを1回使った分カウントしていることになります。
そして最終的にはdp[-1]によって最後の個数を返却します。
Time complexityはループが2つあるので、O（n * nの平方根）、Space complexityはdpを作成しているのでO（n）となります。
以上です。
