Authored by Tony Feng

Created on April 10th, 2022

Last Modified on April 10th, 2022

Understanding Dynamic Programming

Intro

• Dynamic Programming helps to efficiently solve a class of problems that have overlapping subproblems and optimal substructure property.
• Key elements
  • Initialization
  • State-transition Equation
  • Termination

Characteristics

• Overlapping Subproblems
  • Any problem has overlapping sub-problems if finding its solution involves solving the same subproblem multiple times.
• Optimal Substructure Property
  • Any problem has optimal substructure property if its overall optimal solution can be constructed from the optimal solutions of its subproblems.

Dynamic Programming Methods

• Top-down with Memoization
  • In this approach, we try to solve the bigger problem by recursively finding the solution to smaller sub-problems.
  • Whenever we solve a sub-problem, we cache its result so that we can just return the saved result if it’s called multiple times.
• Bottom-up with Tabulation
  • Tabulation is the opposite of the top-down approach and avoids recursion.
  • In this approach, we solve the problem “bottom-up” (i.e. by solving all the related sub-problems first). This is typically done by filling up an n-dimensional table. Based on the results in the table, the solution to the top/original problem is then computed.

Examples

Leetcode 509 Fibonacci Number

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution:
    def fib(self, n: int) -> int:
        if n == 0: return 0
        if n == 1: return 1
        
        dp = [0] * (n + 1)
        dp[0], dp[1] = 0, 1
        
        for i in range(2, n+1):
            dp[i] = dp[i-1] + dp[i-2]   # State-transition Equation

        return dp[n]

Leetcode 62 Unique Paths

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        dp = [[1 for _ in range(n)] for _ in range(m)]
        
        for i in range(0, m):
            for j in range(0, n):
                if i - 1 < 0:
                    dp[i][j] = dp[i][j-1]
                elif j - 1 < 0:
                    dp[i][j] = dp[i-1][j]
                else:
                    dp[i][j] = dp[i-1][j] + dp[i][j-1]
        
        return dp[m - 1][n - 1]    

Reference

• 手把手带你刷Leetcode力扣 - 动态规划 Dynamic Programming
• 手把手带你刷Leetcode力扣 - Leetcode 509
• 手把手带你刷Leetcode力扣 - Leetcode 62
• What is Dynamic Programming?
• Programiz - Dynamic Programming