279.Perfect Squares

Tags: [knapsack], [complete_knapsack], [DP], [rolling_table], [BFS], [trick]

Com: {g}

Link: https://leetcode.com/problems/perfect-squares/\#/solutions

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

For example, given n=12, return3because12 = 4 + 4 + 4; given n=13, return2because13 = 4 + 9.

Credits:
Special thanks to@jianchao.li.fighterfor adding this problem and creating all test cases.

Solution: Knapsack, Complete Knapsack, DP

import math

class Solution(object):
    def numSquares(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n <= 0:
            raise ValueError('the input is invalid')

        squares = [x**2 for x in xrange(1, int(math.sqrt(n)) + 1)]

        # Knapsack problem.
        dp = [sys.maxint for _ in xrange(n + 1)]
        dp[0] = 0

        for i in xrange(len(squares) + 1):
            curr_sq = squares[i - 1]
            for sub_n in xrange(1, n + 1):
                if curr_sq <= sub_n:
                    dp[sub_n] = min(dp[sub_n], dp[sub_n - curr_sq] + 1)

        return dp[n]

Revelation:

• If we want to just fully filled the bag, we should initialize the dp[i][0] = 0, and dp[i][other] = sys.maxint.
• Because this is complete knapsack problem, so the inner loop iteration is from 1 to n. Think about we can use as many as curr_sq, and in the inner loop, each time we just ad one more, until it cannot fit the bag. Reference: http://love-oriented.com/pack/P02.html.
• Don't forget to check 'if curr_sq <= sub_n', if this checking is False, we will not touch dp[sub_n], which is still storing the 'previous' value.

Note:

• Time complexity = O(sqrt(n) * n), num of perfect squares = O(sqrt(n)).

Time Limited Exceeded: Knapsack, Complete Knapsack

import math

class Solution(object):
    def numSquares(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n <= 0:
            raise ValueError('the input is invalid')

        squares = [x**2 for x in xrange(1, int(math.sqrt(n)) + 1)]

        # Knapsack problem.
        dp = [[sys.maxint for _ in xrange(n + 1)] for _ in xrange(len(squares) + 1)]
        for i in xrange(len(squares) + 1):
            dp[i][0] = 0

        for i in xrange(1, len(squares) + 1):
            curr_sq = squares[i - 1]
            for sub_n in xrange(1, n + 1):
                dp[i][sub_n] = dp[i - 1][sub_n]
                k = 1
                while k * curr_sq <= sub_n:
                    dp[i][sub_n] = min(dp[i][sub_n], 
                                       dp[i - 1][sub_n - k * curr_sq] + k)
                    k += 1

        return dp[len(squares)][n]

Solution: BFS, Trick

import math

class Solution(object):
    def numSquares(self, n):
        """
        :type n: int
        :rtype: int
        """
        if not n or n <= 0:
            raise ValueError('The input is invalid')

        # BFS
        queue = set()
        queue.add(n)
        counter = 0
        while queue:
            counter += 1
            tmp_queue = set()
            for curr in queue:
                for x in xrange(1, int(math.sqrt(n)) + 1):
                    sq = x ** 2
                    if curr - sq < 0:
                        break
                    if curr - sq == 0:
                        return counter

                    tmp_queue.add(curr - sq)
            queue = tmp_queue

        return -1

Revelation:

• Starting from number n, each time we just try to subtract one perfect square from it. BFS can help us find the shortest path.
• For saving some memory, each time we iterate all elements in the queue, to check each element with the perfect squares. And using the set as the queue to remove the duplicates.
• 用这种方法做BFS，可以尽早的结束BFS， 避免产生很多children.

Note:

• Time complexity = O(k * sqrt(n)), k is num of times iterations in the outer loop, so k <= n.

Memory Limited Exceeded: BFS

import math

class Solution(object):
    def numSquares(self, n):
        """
        :type n: int
        :rtype: int
        """
        if not n or n <= 0:
            raise ValueError('The input is invalid')

        # BFS
        queue = collections.deque()
        queue.append((n, 0))
        while queue:
            curr, distance = queue.popleft()
            if curr == 0:
                return distance

            for x in xrange(1, int(math.sqrt(n)) + 1):
                sq = x ** 2
                if curr - sq < 0:
                    continue

                queue.append((curr - sq, distance + 1))

        return -1

Note:

• Time complexity = O(k * sqrt(n)), k <= n.