DP Bag

Algorithms
TODO, dp
Catalogue
  1. 1. 279. Perfect Squares
    1. 1.1. Solution1. DP - TLE
    2. 1.2. Solution2. BFS
  2. 2. 322. Coin Change
  • Count
    1. 1. 518. Coin Change 2

    • 279. Perfect Squares

    Solution1. DP - TLE

    • Time O($n\sqrt{n}$), Space: O(n)
    • have no idea why works in python2, but TLE in python3
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    class Solution:
        def numSquares(self, n):
            dp = [float('inf')] * (n+1)
            dp[0] = 0
            for i in range(1, n+1):
                j = 1
                while (j * j <= i):
                    if dp[i-j*j] + 1 < dp[i]:
                        dp[i] = dp[i-j*j] + 1
                    j += 1
            return dp[-1]

    Solution2. BFS

    • Consider a graph which consists of number 0, 1,…,n as its nodes.
    • Node j is connected to node i via an edge if and only if either j = i + (a perfect square number) or i = j + (a perfect square number). Starting from node 0, do the breadth-first search.
    • If we reach node n at step m, then the least number of perfect square numbers which sum to n is m. Here since we have already obtained the perfect square numbers, we have actually finished the search at step 1.
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      class Solution:
          def numSquares(self, n):
              cans = []
              i = 1
              while i * i <= n:
                  cans.append(i * i)
                  i += 1

              queue = [n]
              level = 0
              while queue:
                  level += 1
                  nqueue = set()
                  for remain in queue:
                      for can in cans:
                          if can == remain:
                              return level
                          if can > remain:
                              break
                          nqueue.add(remain-can)
                  queue = list(nqueue)

    322. Coin Change

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    class Solution(object):
        def coinChange(self, coins, amount):
            if amount == 0:
                return 0

            dp = [float('inf')] * (amount+1)
            dp[0] = 0

            for i in xrange(1, amount+1):
                for coin in coins:
                    if i-coin >= 0:
                        dp[i] = min(dp[i], dp[i-coin]+1)

            return -1 if dp[-1] == float('inf') else dp[-1]

    Count

    518. Coin Change 2

    • Why use for loop in this order??? coin first, then amount?
      1
      2
      3
      4
      5
      6
      7
      8
      class Solution(object):
          def change(self, amount, coins):
              dp = [0] * (amount+1)
              dp[0] = 1
              for coin in coins:
                  for i in range(coin, amount+1):
                      dp[i] += dp[i-coin]
              return dp[-1]
    Share