Dynamic Programming Explained

Brief Definition

Dynamic programming refers to simplifying a complicated problem by breaking it down into simpler sub-problems in a recursive manner. Wherever we see a recursive solution that has repeated calls for same inputs, we can optimize it using dynamic programming. The main idea is to store the results of sub-problems to avoid re-computing.

How to Solve

  • Decide State
    A state can be uniquely defined by a set of parameters
  • Define Transition
    Transitions tell us the relationships between states

It can be hard to come up with a dynamic programming solution at first, so I always solve it in a recursive way, and then convert it to dynamic programming solution, this could cause less pain in defining states and transitions.

Fibonacci Case

Fibonacci (n) = 1; if n = 0
Fibonacci (n) = 1; if n = 1
Fibonacci (n) = Fibonacci(n-1) + Fibonacci(n-2)

An intuitive way to solve it:

def fib(n):
    if n == 0 or n == 1:
        return 1
    else:
        return fib(n-1) + fib(n-2)

But when you call fib(4), fib(2) will be computed twice. The re-computing will cause a lot of waste and slow down the speed of calculation when n gets larger.

To optimize it using dynamic programming: 1. Decide State: fib(n) - nth elements in the Fibonacci numbers 2. Define Transition: fib(n) = fib(n-1) + fib(n-2)

So define an array to store the results of sub-problems:

def fib(n):
    fib_nums = [0] * n
    fib_nums[0] = 1
    fib_nums[1] = 1
    for i in range(2, n+1):
        fib_nums[i] = fib_nums[i-1] + fib_nums[i-2]

Problems in LeetCode

Regular Expression Matching
Given an input string (s) and a pattern (p), implement regular expression matching with support for ‘.’ and ‘*’ .

class Solution:
## recursive way
#     def isMatch(self, s: str, p: str) -> bool:
#         if not p:
#             return not s
        
#         first_match = bool(s) and p[0] in {s[0], '.'}
        
#         if len(p) >= 2 and p[1] == '*':
#             return (self.isMatch(s, p[2:]) or 
#                    first_match and self.isMatch(s[1:], p))
#         else:
#             return first_match and self.isMatch(s[1:], p[1:])

## dynamic programming       
    def isMatch(self, s: str, p: str) -> bool:
        # construct the matrix
        dp = [[False] * (len(p)+1) for _ in range(len(s)+1)]
        
        dp[-1][-1] = True
        for i in range(len(s)+1)[::-1]:
            for j in range(len(p))[::-1]:
                first_match = i < len(s) and p[j] in [s[i], '.']
                if j+1 < len(p) and p[j+1] == '*':
                    dp[i][j] = dp[i][j+2] or first_match and dp[i+1][j]
                else:
                    dp[i][j] = first_match and dp[i+1][j+1]
        return dp[0][0]

This is a hard one. If there is no ‘*’ , which matches zero or more of the preceding element, then we only need to compare each character one by one. With ‘*’ present we need to check many different suffixes of the text and see if they match the rest of the pattern. The recursive version is straightforward.

After finishing the recursive one, the state is clear: define dp[i][j] indicating s[:i] and p[:j] match. The transition would be a reverse of the recursive call.

Edit Distance
Given two words word1 and word2, find the minimum number of operations required to convert word1 to word2.
You have the following 3 operations permitted on a word:
1. Insert a character
2. Delete a character
3. Replace a character

class Solution:         
    def minDistance(self, s1: str, s2: str) -> int:
        # def operation(s1, s2):
        #     if not s1 or not s2:
        #         return abs(len(s1) - len(s2))
        #     elif s1[0] == s2[0]:
        #         return operation(s1[1:], s2[1:])
        #     else:
        #         replace = operation(s1[1:], s2[1:])
        #         remove = operation(s1[1:], s2)
        #         insert = operation(s1, s2[1:])
        #         return 1 + min(replace, remove, insert)
        # return operation(word1, word2)
        
        ## dp matrix, dp[i][j] -> operation(s1[i:], s2[j:])
        dp = [[0]*(len(s2)+1) for _ in range(len(s1)+1)]
        for i in range(len(s1)+1)[::-1]:
            for j in range(len(s2)+1)[::-1]:
                if i >= len(s1) or j >= len(s2):
                    dp[i][j] = abs(len(s1[i:])-len(s2[j:]))
                elif s1[i] == s2[j]:
                    dp[i][j] =  dp[i+1][j+1]
                else:
                    dp[i][j] = 1 + min(dp[i+1][j+1], dp[i+1][j], dp[i][j+1])
        return dp[0][0]

Again, start from the recursive solution. And the state is a cache of its intermediate values. The transition, the same, is a reversion of the recursive call.

Chuanrong Li

Read more posts by this author.