Dynamic programming

Author

Pham Nguyen Hung

Published

July 21, 2023

Dynamic programming

Definition

A technique for solving complex problems by breaking them down into smaller subproblems and solving each subproblem only once. The results are stored inside a cache, and are reused whenever the same subproblem needs to be solved again.

Dynamic programming is a step forward from recursion, trading memory efficiency for time efficiency. However, with clever caching (and clear thinking), both time and memory complexities can be improved.

Dynamic programming, following recursion, also has two approaches: top-down and bottom-up. In the top-down approach, it seems that all I need is a cache i.e., memoization of values to avoid recomputation while carrying out business as usual from the the top. In the bottom up approach, it is harder and requires knowing the nuances of the problem as the problem is solved iteratively from bottom up.

Problems

0. Sort an Array

Intuition

Algorithm

Complexity

  • Time complexity:

  • Space complexity:

Code

from typing import List

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        self._mergeSort(nums)
        return nums
    
    def _mergeSort(self, nums: List[int]) -> None:
        if len(nums) > 1:
            mid = len(nums) // 2
            left_half = nums[:mid]
            right_half = nums[mid:]

            self._mergeSort(left_half)
            self._mergeSort(right_half)

            self._merge(nums, left_half, right_half)
    
    def _merge(self, nums: List[int], left_half: List[int], right_half: List[int]) -> None:
        left_pointer = right_pointer = num_pointer = 0

        while left_pointer < len(left_half) and right_pointer < len(right_half):
            if left_half[left_pointer] < right_half[right_pointer]:
                nums[num_pointer] = left_half[left_pointer]
                left_pointer += 1
            else:
                nums[num_pointer] = right_half[right_pointer]
                right_pointer += 1
            num_pointer += 1
        
        if left_pointer < len(left_half):
            nums[num_pointer:] = left_half[left_pointer:]
        elif right_pointer < len(right_half):
            nums[num_pointer:] = right_half[right_pointer:]

1. Fibonacci Number

Intuition

From the top, solving for the \(n^{th}\) Fibonacci number requires me to calculate the two smaller ones i.e. \((n-1)^{th}\) and \((n-2)^{th}\) and sum them together. However, in calculating the \((n-1)^{th}\) Fibonacci number, I also needs the \((n-2)^{th}\) one, and both of them needs the \((n-3)^{th}\) ones. In the naive approach, I will need to calculate the same value exponentially, leading to a \(O(2^n)\) time complexity. Worse, the recursion call stack matches the time complexity i.e.

To optimize this, from the recursion solution, memoization can be used. The value that has already been calculated can be cached, and reused upon request. The time and memory complexities reduces from exponential to linear \(O(n)\) with this caching.

From a bottom-up perspective, one can do away with recursion and just use iteration. The value of the next number is calculated from just two previous numbers. Hence, only two previous numbers need caching, and used values can be discarded. This leads to \(O(1)\) memory while still having the \(O(n)\) time complexity.

Algorithm

  • Top-down
    1. For the nested rob function, the parameter is n and a dictionary.
    2. Base cases: n is smaller than 2, or n has already been cached.
    3. Recursive case: call the memoization function on the two previous numbers with the same parameters.
    4. Return the result.
  • Bottom-up
    1. Define the base case when n is smaller than 2 and the variables storing two previous numbers.
    2. Iterate n-1 times, storing the current number i.e., the second previous to the first previous and storing the sum of them to the second previous.
    3. Return the result.

Complexity

  • Time complexity: \(O(n)\) - as explained above.

  • Space complexity: \(O(n)\) for top-down, \(O(1)\) for bottom-up.

Code

Top-down

class Solution:
    def fib(self, n: int) -> int:
        def memoize(n: int, cache: dict):
            if n < 2:
                return n
            if n in cache:
                return cache[n]
        
            cache[n] = memoize(n - 1, cache) + memoize(n - 2, cache)
            return cache[n]
        
        return memoize(n, {})

Bottom-up

class Solution:
    def fib(self, n: int) -> int:
        if n < 2:
            return n
        # Bottom-up
        previousOne = 0
        previousTwo = 1
        for _ in range(n - 1):
            # current = previousTwo
            # previousTwo = previousOne + previousTwo
            # previousOne = current
            previousOne, previousTwo = previousTwo, previousOne + previousTwo
        
        return previousTwo

2. Climbing Stairs

Intuition

The incredible intuition hits me about the arrangement of the stairs. It is the problem of how many permutations with repetition for some number of 1 steps and some number of 2 steps. The start case is when all steps I take is 1 step i.e., I have \(n\) 1-step steps. The number of permutations is 1 - all of them are the same. To get to the next case, I assume that now I can take only \(1\) 2-step step, which means I have \(n-2\) 1-step steps. I need to calculate the number of permutations for \(n-2\) repetitive instances of A and \(1\) instance of B. And then it continues until I have only \(0\) or \(1\) 1-step step to take, depending on the oddity of the number. I can then just sum together the value. A small notice: the value of permutations with repetition in this case is equal to choosing a certain number of 2-step steps out of the total number of 1-step and 2-step steps I can make. However, this is no dynamic programming - only maths.

In the dynamic programming approach, the observation is this: at the last, or the \(n^{th}\) step, there is only 1 way to proceed: do nothing. At the \((n-1)^{th}\) step, there is only 1 way: take 1 step to the end. At the \((n-2)^{th}\) step, there are 2 ways: take 1 step to the \((n-1)^{th}\) step, or take 2 steps to the end. At the \((n-3)^{th}\) step, I can take 1 step to the \((n-2)^{th}\) step, which provides me with 2 different choices, or I can take 2 steps to the \((n-1)^{th}\) step, which provides me with 1 choice, yielding 3 in total. The pattern here is that the number of different ways to the end from a step is the sum of numbers of different ways to the end of two steps ahead, which coincides with the Fibanacci number.

Algorithm

  1. Base case: return n if n is smaller than 4
  2. Iterative case: calculate it similar to the Fibonacci number for the remaining tiles and return.

Complexity

  • Time complexity: \(O(n)\) - True for both approaches.

  • Space complexity: \(O(1)\) - True for both approaches.

Code

  • Combinatorics
from math import factorial

class Solution:
    def climbStairs(self, n: int) -> int:
        count = 0
        num_ones = n
        num_twos = 0
        while num_ones >= 0:
            # count += comb(num_ones + num_twos, num_twos)
            count += factorial(num_ones + num_twos)//(factorial(num_ones)*factorial(num_twos))
            num_twos += 1
            num_ones -= 2
        return count
  • Dynamic Programming
class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 3:
            return n
        prevNum, currNum = 2, 3

        for i in range(4, n + 1):
            temp = prevNum + currNum
            prevNum = currNum
            currNum = temp
        return currNum

3. House Robber

Intuition

“To rob or not to rob”, that’s the question you faced at every house. Together with the rule of not robbing adjacent house, you can form a recursion solution. Of course, maximum recursion depth stack reached. You now remember memoization i.e., the dictionary that you should use to cache the result, adding a base case to the helper function, remember to store result each time before returning the value. Voila, top-down (fake) dynamic programming.

For bottom-up dynamic programming, let’s jump to the end i.e., the \(n^{th}\) house. Imagine that every position stores the maxium sum up to that position. You can either rob that house plus the maximum sum from the first to the \((n-2)^{th}\) house, or you ignore that house and try the rest, which is the maximum sum stored at the \((n-1)^{th}\) house. You just realized that to calculate the maximum amount “robable” up to a house, you just need the values for two houses immediately before it. Again, Fibonacci number.

Algorithm

  1. Initialize the variables storing the maximum sum so far to 0.
  2. Iterate the array, push the later value to the former, and set the later to the maximum between the current house plus the former value and current value at the later.
  3. Return the later value.

Complexity

  • Time complexity: \(O(n)\) - True for both cases

  • Space complexity: \(O(n)\) for top-down, \(O(1)\) for bottom-up.

Code

  • Top-down
class Solution:
    def rob(self, nums: List[int]) -> int:
        best = {}
        def rob(index):
            if index >= len(nums):
                return 0
            if index in best:
                return best[index]

            total = max(rob(index+2),rob(index+3))
            best[index] = total + nums[index]
            return total + nums[index]

        return max(rob(0),rob(1))
  • Bottom-up
class Solution:
    def rob(self, houses: List[int]) -> int:
        prev_house, curr_house = 0, 0
        for house in houses:
            prev_house, curr_house = curr_house, max(house + prev_house, curr_house)
        return curr_house

4. Unique Paths

Intuition

Let’s go 2D as if 1D is not irritable enough. Anyway, here I have a robot that wants to go from the top left corner to the bottom right corner, only allowed to move right and down. I need to find the number of unique paths that the robot can move.

The trick of the trade is imagining a 2D matrix, each square storing a piece of information e.g., number of unique paths one can get to the end from the cell. Another trick is filling one square at a time in reverse. Another trick is assumiung an all-zero padding (some use outside convolution). Now I go bottom-up. At the destination, there is one go to reach it: doing nothing. To the tile directly above and directly to the left, there is one way to reach the end: just move. This is actually true along the last column and the last row: in every cell, there is just 1 way to reach the end. By fumbling (with pen and paper) with the matrix, one may realize that the unique paths from a cell is the sum of the unique paths from the tile directly to the right and directly below, which is intuitive given these are the only cells I can go from the current cell.

Algorithm

  1. Initialize a row of all 1s at the bottom.
  2. Iterate through every other row in the matrix backwardly.
    1. For each row, iterate the columns backward from the second to last position. The value of each row will be the number of routes from that to the bottom right position, calculated by summing the position right after and the node itself (the last position will always be initialized as 1, because there is only 1 way: all the way down).
  3. Return the value stored in the top left corner.

Complexity

  • Time complexity: \(O(m \times n)\) - iterate through every position in the matrix.

  • Space complexity: \(O(n)\) - maintaining the values in 1 row at a time.

Code

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        curRow = [1] * n
        for _ in range(m - 2, -1, -1):
            for col in range(n - 2, -1, -1):
                curRow[col] += curRow[col + 1]
        return curRow[0]

5. Unique Paths II

Intuition

This time, there can be obstacle(s) lying around the matrix. The good news is that the algorithm stays the same, except 1. I cannot skip the last row in case there are obstacles there and 2. the obstacle position needs setting to 0 possible way and carrying to the next row.

Algorithm

  1. Initialize the bottom row as 0s except 1 in the bottom right corner.
  2. Iterate the rows backward:
    1. Iterate the columns backward:
      1. If the position is an obstacle, set the value in the row to 0.
      2. Else, if it is not the last position, add the value of the position right after to it.
  3. Return the value stored at the top left corner.

Complexity

  • Time complexity: \(O(m \times n)\) - iterate through every position in the matrix.

  • Space complexity: \(O(n)\) - maintaining the values in 1 row at a time.

Code

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        m, n = len(obstacleGrid), len(obstacleGrid[0])
        tempRow = [0] * n
        tempRow[n - 1] = 1
        for row in range(m - 1, -1, -1):
            for col in range(n - 1, -1, -1):
                if obstacleGrid[row][col]:
                    tempRow[col] = 0
                elif col + 1 < n:
                    tempRow[col] = tempRow[col + 1] + tempRow[col]
        return tempRow[0]

6. Longest Common Subsequence

Intuition

Algorithm

Complexity

  • Time complexity:

  • Space complexity:

Code

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        dim1, dim2 = len(text1), len(text2)
        prevRow, currRow = [0] * dim2, [0] * dim2
        for i in range(dim1):
            for j in range(dim2):
                if j > 0:
                    if text1[i] == text2[j]:
                        currRow[j] = prevRow[j - 1] + 1
                    else:
                        currRow[j] = max(currRow[j - 1], prevRow[j])
                else:
                    currRow[j] = 1 if text1[i] == text2[j] else prevRow[j]
            prevRow = currRow[:]
            print(prevRow)
        return currRow[-1]

7. Coin Change

Intuition

Algorithm

Complexity

  • Time complexity:

  • Space complexity:

Code

BFS

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        if amount == 0:
            return amount
        seen = set()
        remainders = [amount]
        count = 0
        
        while remainders:
            count += 1
            temp = []
            for val in remainders:
                for coin in coins:
                    rem = val - coin
                    if rem == 0:
                        return count
                    elif rem > 0 and rem not in seen:
                        seen.add(rem)
                        temp.append(rem)
            remainders = temp

        return -1

Dynamic programming

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp = [float("inf")] * (amount + 1)
        dp[0] = 0

        for a in range(1, amount + 1):
            for coin in coins:
                if a - coin >= 0:
                    dp[a] = min(dp[a], 1 + dp[a - coin])
        
        return dp[amount] if dp[amount] != float("inf") else -1

8. Partition Equal Subset Sum

Intuition

This is somewhat similar to the Subset problem. Basically, the answer is False if the sum of whole array is odd, and True if there exists a subset sum equal to half of the total sum. Hence, the problem can be reduced to constructing the sum for all subsets in of the array, return True if a subset sum satisfies the condition.

To construct the solution it is better to use a set to prune duplicated results.

Algorithm

  1. Check that total sum is even.
  2. Initialize the current subset sum with 0 and the target as total // 2.
  3. Iterate through the array.
    1. Initialize the next subset sum set with a copy of the current one.
    2. Add the current element in the array to each sum in the current subset sum set. If the new value is equal to the target, return True, else add the value to the set.
    3. If reach the end, update the current subset sum set.
  4. Return False by default.

Complexity

  • Time complexity: \(O(n \times \sum \text{nums})\) - Iterate through the array, for each iteration iterate through the set which has a maximum size as below.

  • Space complexity: \(O(\sum \text{nums})\) - The maximum size of the set. Theoretically, it can contain all numbers from 0 to the total sum of the array.

Code

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        total = sum(nums)
        if total % 2:
            return False
        
        currSubsetSum = set()
        currSubsetSum.add(0)
        target = total // 2

        for i in range(len(nums)):
            nextSubsetSum = currSubsetSum.copy()
            for subset_sum in currSubsetSum:
                if subset_sum + nums[i] == target:
                    return True
                nextSubsetSum.add(subset_sum + nums[i])
            currSubsetSum = nextSubsetSum
        return False