optimize perfect squares problem similar to coin change in python-CodePudding

I have a solution for coin change here: Coin change leetcode in python

since the question of the perfect square is similar to the coin change problem, I want to solve it with my method instead of memorizing other's solutions.

I think the only difference between two questions is for perfect squares we are going to have a nums array that consists of only perfect squares: [1,4,9,25..]. I believe I solved the problem correctly but having a time limit exceeded error for bigger inputs (last executed input 8328). Here is the perfect squares question:

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.

I need help optimizing the code:

class Solution:
    def numSquares(self,n:int)->int:
        nums=[]
        # create square numbers list till n
        for i in range(1,n 1):
            if self.is_perfect(i):
                nums.append(i)
                print(nums)
        def dfs(target, memo={}):
            if target in memo:
                return memo[target]
            if target == 0:
                return []
            if target < 0:
                return None
            shortest_combination = None
            for num in nums:                
                remainder = target - num
                result = dfs(remainder)
                # make sure not if result because result might be [] which yields to False
                if result != None:
                    #combination = result [num]
                    # this seems more efficient
                    combination = [*result, num]
                    if shortest_combination == None or len(combination) < len(shortest_combination):
                        shortest_combination = combination
            memo[target] = shortest_combination
            return shortest_combination
        return len(dfs(n))
    def is_perfect(self,n):
        for i in range(1,n 1):
            if i*i>n:
                return False
            if i*i==n:
                return True        
        return False

CodePudding user response：

Your code is slow because you're not really memoizing anything. When you do:

result = dfs(remainder)

The function will be called with an empty dictionary, not with your memo dictionary, therefore the first if that checks whether target is in memo will never be true. So you're effectively not doing any memoization.

The best fix is to move memo outside dfs entirely, declare it in numSquares. Never use mutable objects (such as lists and dictionaries) as default parameter values. Getting used to doing it like this will help avoid making this easy to make mistake in the future.

Your code is also slow because you are memoizing lists. You are computing this recurrence:

dfs(target) = list with the minimum number of perfect squares that sum to target

But you are returning its length in the end, so you don't need the actual list. And even if you did, it can usually be reconstructed from the subproblems anyway.

Instead try to compute:

dfs(target) = minimum number of perfect squares that sum to target

You can do this with a couple of changes:

First:

        if target == 0:
            return []

You should return either 1 or 0 here because 0*0 = 0 or because 0 perfect squares have a sum of 0. Up to you how you interpret this. You probably want 0 since you had [] before.

        shortest_combination = None
        for num in nums:                
            remainder = target - num
            result = dfs(remainder)
            # make sure not if result because result might be [] which yields to False
            if result != None:
                #combination = result [num]
                # this seems more efficient
                combination = [*result, num]
                if shortest_combination == None or len(combination) < len(shortest_combination):
                    shortest_combination = combination

This can be adapted to our new counting context:

        shortest_combination = INFINITY # a very large number that can never be the answer, for example 10**20
        for num in nums:                
            remainder = target - num
            result = dfs(remainder)
           
            if result != None and result   1 < shortest_combination:
                shortest_combination = result   1

CodePudding user response：

The way you populate the nums (and it's better be called squares) is quite suboptimal. Consider instead
```
  i = 1
  while i*i <= n:
      squares.append(i*i)
      i  = 1
```
It may also be easily converted to a list comprehension.

Now, since all squares - except, perhaps, the last one are smaller that n, testing for perfect-squareness of n is just
```
  if n == squares[-1]:
```
The four squares theorem shall lead to a drastic speedup. You don't want to follow up a sequence if it reaches a length of 4 and still does not add up to a target.

Perhaps is is not what you are after, but it is what the problem is after.

With this knowledge, consider an alternative approach:

Since len(squares) is approximately sqrt(n), a computation of sums of two squares takes O(n). Make it a set.
Given a list of squares, and a ser of 2-sums, determining whether or not a target number is a sum of three squares is trivial.
Now we may invoke a heavy artillery. If the target number is neither a square, nor the sum of two, nor the sum of three, it must be a sum of four.