Leetcode 279. Perfect Squares (Python)

Related Topic

Dynamic-Programming.

Description

Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, …) which sum to n.

Sample I/O

Example 1

Input: n = 12
Output: 3 
Explanation: 12 = 4 + 4 + 4.

Example 2

Input: n = 13
Output: 2
Explanation: 13 = 4 + 9.

Methodology

This question can be solved by Dynamic Programming. However, dp is not the best solution.

It took me long time to think about the dynamic programming solution. Here is my process of thinking:

1. If the value is made up by square, then the least number of perfect square is 1.
2. However, usually each value will have one more perfect square than previous value. Now I can get most number of perfect square which is dp[i-1]+1. Is there any way to make this number less or is there any way to calculate the number of perfect square differently?
3. Continue to the second one. Yes. If you can eliminate 1 perfect square from current value then you probably will have a smaller number of square than dp[i-1]+1. But which square to eliminate?
4. The proper square to eliminate is start from the 1st until the the last smaller one to the current value. There you go, we got the pattern.

Base case:

We create dp list and init each value to 1 because there at least 1 number of perfect square. Init 0 index as 0 because the number of perfect square for 0 is 0.

We also need a create a list of squares [1,4,9,16,…] The last square should never exceed the input number.

Pattern

Iterate the value if the value is in square, we skip the iteration to next. Otherwise, we give the most number of square to the current value for compare, each time we will update the number of square for current value. This means, compare the current number of square to the the new number of square which is got from square elimination until we get minimum.

Code 1

def numSquares(self, n: int) -> int:
        squares = [i**2 for i in range(1, int(n**0.5)+1)]
        dp=[1]*(n+1)
        dp[0] = 0
        for i in range(1,n+1):
            if i in squares:
                continue
            dp[i]=dp[i-1]+1
            for square in squares:
                if i < square:
                    break
                dp[i]=min(dp[i], dp[i-square]+1)
        return dp[-1]

BigO

We iterate all dp array, it will cost O(n), inside the first iteration, we need to iterate the squares which is O(√n) So the total time complexity is O(n√n)