Dynamic Programming

Summary

The key idea to solve a dynamic programming (DP) problem is to break it down into subproblems and write the state transition function. In the mean-time, DP problem might have redundant subproblems, so we can use memoization or a DP table to reduce the redundant computation.

Fibonacci Sequence (Leetcode 509)

Brute Force Solution

The brute force solution is to use recursion to calculate the Fibonacci number. However, this solution has exponential time complexity (\(\gO(2^n)\))

class Solution:
    def fib(self, n: int) -> int:

        if n <= 0:
            return 0
        elif n == 1:
            return 1
        else:
            return self.fib(n-1) + self.fib(n-2)

Memoization Solution

To reduce the redundant computation, we can use memoization to store the intermediate results.

class Solution:
    def fib(self, n: int) -> int:
        self.mem = [False] * (n+1)
        return self.dp(n)


    def dp(self, n):
        if n <= 0:
            return 0
        elif n == 1:
            return 1

        if not self.mem[n]:
            self.mem[n] = self.dp(n-1) + self.dp(n-2)

Bottom-up Solution (Iterative)

We may not need to store all the intermediate results since the current state only depends on the previous two states. Thus, we can use a bottom-up approach to reduce the space complexity to \(\gO(1)\). The state transition function is \(f(n) = f(n-1) + f(n-2)\).

class Solution:
    def fib(self, n: int) -> int:

        if n == 0 or n == 1:
            return n

        fib_n1, fib_n2 = 1, 0

        for i in range(2, n+1):
            fib_n = fib_n1 + fib_n2
            fib_n1, fib_n2 = fib_n, fib_n1

        return fib_n

Coin Change (Leetcode 322)

Brute Force Solution

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        return self.dp(coins, amount)


    def dp(self, coins, amount):

        if amount == 0:
            return 0
        elif amount <= 0:
            return -1

        res = float('inf')
        for coin in coins:
            count = self.dp(coins,amount - coin)

            if count < 0:
                continue

            res = min(res, count + 1)

        return res if res != float('inf') else -1

Memoization Solution

The following is a wrong solution because the memoization table is not updated correctly.

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        self.mem = [-1] * (amount + 1) # Use another value to indicate it is not calculated yet
        return self.dp(coins, amount)


    def dp(self, coins, amount):

        if amount == 0:
            return 0
        elif amount < 0:
            return -1

        if self.mem[amount] > 0:
            return self.mem[amount]

        res = float('inf')
        for coin in coins:
            count = self.dp(coins,amount - coin)

            if count < 0:
                continue

            res = min(res, count + 1)

        if res != float('inf'):
            self.mem[amount] = res # This should be updated to -1 if res == float('inf')

        return self.mem[amount]

The correct memoization solution is as follows:

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        self.mem = [-2] * (amount + 1)
        return self.dp(coins, amount)


    def dp(self, coins, amount):

        if amount == 0:
            return 0
        elif amount < 0:
            return -1

        if self.mem[amount] != -2:
            return self.mem[amount]

        res = float('inf')
        for coin in coins:
            count = self.dp(coins,amount - coin)

            if count ==-1:
                continue

            res = min(res, count + 1)

        if res != float('inf'):
            self.mem[amount] = res
        else:
            self.mem[amount] = -1

        return self.mem[amount]