Algorithm - Dynamic Programming (2)

Leetcode Dynamic Programming Problem Collection (2)

• 322.Coin Change
• 55.Jump Game
• 62.Unique Paths
• 300.Longest Increasing Subsequence
• 91.Decode Way

322. Coin Change

for example coins = [1,2,5], x = 11
Three cases for selecting the last coin:

1. the last coin is $1, f(x) = f(x - 1) + 1
2. the last coin is $2, f(x) = f(x - 2) + 1
3. the last coin is $5, f(x) = f(x - 5) + 1

Hense, f(x) = min(f(x - 1), f(x - 2), f(x - 5)) + 1
we can use recursion to eaisly get the global optimized result, with lot of redandunt calculation (TLE)
Or we can pre-calculate and save f(0) ~ f(x), to avoid repeating calculation.
f(0) = 0 is the base case. x - coin < 0 is invalid, for instance, f(1) = -1, no result.

Bottom up

def coinChange(self, coins: List[int], amount: int) -> int:
    dp = [amount + 1] * (amount + 1)
    dp[0] = 0
    for i in range(len(dp)):
        for coin in coins:
            if i - coin >= 0:
                dp[i] = min(dp[i], 1 + dp[i - coin])
    return -1 if dp[amount] == amount + 1 else dp[amount]

Top down

def coinChange(self, coins: List[int], amount: int) -> int:
        
    def change(amount):
        if amount in found:
            return found[amount]
        
        if amount == 0:
            return 0
        
        if amount < 0:
            return -1
        
        res = float('inf')
        
        for coin in coins:
            cur = change(amount - coin)
            if cur != -1:
                res = min(res, 1 + cur)
        
        found[amount] = res if res != float('inf') else -1
        return res
    
    found = {}
    change(amount)
    return found[amount] if amount != 0 else 0

55. Jump Game

This is a top-down solution. start the the second last element, if nums[i] + i >= last element

def canJump(self, nums: List[int]) -> bool:
    last = len(nums) - 1
    
    # from the second last element
    for i in range(len(nums) - 2, -1, -1):
        if (nums[i] + i) >= last:
            last = i
    
    return last == 0

62. Unique Paths

If you draw the board, for example m = 3, n = 7, then fill in the number of ways you can get to that a cell, the right-bottom coner is thr right resule. A bottom-up solution.

1, 1, 1, 1,  1,  1,  1
1, 2, 3, 4,  5,  6,  7
1, 3, 6, 10, 15, 21, 28

def uniquePaths(self, m: int, n: int) -> int:
    paths = [[1] * n for _ in range(m)]
    for r in range(1, m):
        for c in range(1, n):
            paths[r][c] = paths[r - 1][c] + paths[r][c - 1]
    return paths[-1][-1]

300. Longest Increasing Subsequence

I don’t think anyone can really thinkof the greedy + binary search solution. Probaly excepting the author, and pro poker players?
Anyway, here’s the DP solution. Time complexity is O(n^2). dp table logs the LIS ending with nums[i]

def lengthOfLIS(self, nums: List[int]) -> int:
    dp = [1] * len(nums)
    res = 1
    for i in range(len(nums)):
        for j in range(i):
            if nums[i] > nums[j]:
                dp[i] = max(dp[i], dp[j] + 1)
        res = max(res, dp[i])
    return res

91. Decode Way

Recursion with memorization. If you draw down the decision tree, that will be pretty straightward.

def numDecodings(self, s: str) -> int:

    def decode(s):
        if s in memo:
            return memo[s]
        if s[0] == '0':
            return 0
        if len(s) == 1:
            return 1
        
        ways = decode(s[1:])
        if int(s[:2]) <= 26:
            ways += decode(s[2:])
        memo[s] = ways
        return ways
    
    memo = {'': 1}
    return decode(s)

DP

def numDecodings(self, s: str) -> int:
    if s[0] == '0':
        return 0
    elif len(s) < 2:
        return 1
    
    dp = [0] * len(s)
    dp[0] = 1
    dp[1] += s[1] != '0'
    dp[1] += 10 <= int(s[:2]) <= 26
    
    for i in range(2, len(s)):
        
        # single digit
        if s[i] != '0':
            dp[i] += dp[i - 1]
        
        # double digits
        if 10 <= int(s[i - 1 : i + 1]) <= 26:
            dp[i] += dp[i - 2]
    return dp[-1]