Leetcode 279 Solution

This article provides solution to leetcode question 279 (perfect-squares)

https://leetcode.com/problems/perfect-squares

Solution

class Solution: def numSquares(self, n: int) -> int: dp = [sys.maxsize] * (n + 1) dp[0] = 0
for i in range(n): v = dp[i]
k = 1 while k * k + i <= n: dp[k * k + i] = min(v + 1, dp[k * k + i]) k += 1
return dp[-1]