一題多解 用DP、BFS去解 Pefect Square 完全平方數的化簡_Leetcode #279
題目敘述
給定一個正整數n，請找出最少用幾個完全平方數，可以讓他們的總和為n?
例如 n=12，最少用3個完全平方數就可讓他們的總和為n，因為12 = 4 + 4 + 4
測試範例
Example 1:
Input: n = 12
Output: 3
Explanation: 12 = 4 + 4 + 4.
Example 2:
Input: n = 13
Output: 2
Explanation: 13 = 4 + 9.
約束條件
Constraints:
1 <= n <= 10^4
輸入的n值介於1~一萬之間。
演算法 映射到Coin Change 最精簡找零
其實Pefect Square這題可以很漂亮的化簡到以前學過的Coin Change 最精簡找零DP模型，怎麼說呢?
把n值視為欲找零的金額，把完全平方數視為銅版即可。
也就是說
DP[ n ] = min( DP[n-1], DP[n-4], DP[n-9], ...) + 1
原本題目所求是用最少的完全平方數去湊出n值。
映射到Coin Change之後，等價的問題就是
用最少的完全平方面額的銅版，去湊出n元。
接下來就是依樣畫葫蘆，稍微修改一下，套上 Coin Change的DP動態規劃演算法即可。
這一題剛好以前也有錄過教學影片，提供給讀者作為參考。
示意圖 映射到Coin Change 最精簡找零
程式碼 映射到Coin Change 最精簡找零
class Solution:
def numSquares(self, n: int) -> int:
INF = sys.maxsize
dp = [ INF for _ in range(n+1) ]
dp[0] = 0
root = 1
square = root*root
# for each square number 1, 4, 9, 16, 25...
while( square <= n ) :
# update dp value for number from square to n
for i in range(square, n+1) :
dp[i] = min( dp[i], dp[i-square]+1 )
# go to next square number
root += 1
square = root*root
return dp[n]
複雜度分析 映射到Coin Change 最精簡找零
時間複雜度:
等價Coin Change找零問題 = O( coin * n ) = O( sqrt(n) * n)
因為銅版面額已知都必須是完全平方數。
空間複雜度:
耗費在DP table上，從DP[0] 記錄到 DP[n]，所需空間為O( n )
演算法 更優雅的BFS 廣度優先搜索 解 等權重圖的最短路徑
承接之前的觀念，既然我們已經知道可以映射到Coin Change最精簡找零，其實我們還可以搭配逆向思考，這樣看。
用最少的平方數 湊出 n 值，其實就相當於
從0元，開始加銅版(當然，在這題，銅版的面額都是完全平方數)，最少加幾次可以湊出n元？
那麼，再搭配圖論的觀點一起看，其實就是0元 -> n元 的最短路徑問題，途中每個可能的金額可以視為一個節點。其中，彼此可以藉由增加銅版抵達的節點，有一條邊連著。
程式碼 BFS廣度優先搜索 解 等權重圖的最短路徑
class Solution:
def numSquares(self, n: int) -> int:
coins = [x**2 for x in range(1, 101) if x*x <= n ]
visited = set()
queue = [0]
# Step count
# = minimal decomposition of $n
# = minimal coin change of $n
step = 0
# Start traverse from $0, each step take a coin, until we reach $n
while queue:
next_queue = []
for cur in queue:
if cur in visited: continue
visited.add(cur)
if cur == n:
return step
# Take a coin
for coin in reversed(coins):
if cur + coin > n: continue
elif cur + coin == n: return step+1
next_queue.append( cur + coin )
step += 1
queue = next_queue
return -1
複雜度分析 BFS廣度優先搜索 解 等權重圖的最短路徑
時間複雜度:
一定有解，因為最差情況就是用一元慢慢去湊，肯定湊的到n元。
最差情況下為$0 -> $1 -> $2 -> ... -> $n
所需時間為O(n)
空間複雜度:
耗費在BFS queue上，分析流程同上，queue最大長度為O(n)。
補充
其實這題還有一個純數學的四平方數定理的解法，但是為了某一題去記憶這種特殊的證明和化簡式 CP值不高，就留給有興趣額外鑽研的讀者研究囉。
關鍵知識點
從題目的規則和範例去推敲背後的數學結構，發現可以化簡到以前學過的Coin Change最精簡找零的DP 模型。
更進一步，結合圖論的觀點，還可以發現這題其實就是在找 零元 -> n元的最短路徑。可以用BFS廣度優先搜索高效率地解開來。
Reference:
[1] Perfect Squares - LeetCode by DP + Coin Change
[2] Perfect Squares - LeetCode by BFS
