wshs0713's blog

Programming notes

0%

[Algo.] Dynamic Programming

Posted on Disqus:
4.9k 4 mins.

source: https://www.geeksforgeeks.org/dynamic-programming/#when-to-use-dynamic-programming-dp
source: https://www.geeksforgeeks.org/dynamic-programming/#when-to-use-dynamic-programming-dp

Introduction

Dynamic Programming (DP) 是一種解決複雜問題的方法，主要是透過將問題拆分成較簡單的子問題，解出並儲存每個子問題的結果，進而求得複雜問題的解。

When to use Dynamic Programming?

Overlapping Subproblems 重疊子問題

複雜的問題可以被拆解成多個子問題，而這些子問題都是有規律、重複的。例如：費氏數列: 0, 1, 1, 2, 3, 5, 8, 13, …, 每一個數字都是前兩個數字的總和。

Optimal Substructure 最優子結構

最優子結構是指將子問題的最優結果結合起來，以達到複雜問題的最優結果。例如：找 source node to destination node 的最小成本路徑，可以拆分成：

  • 從 source node 到每個中間節點的最小成本路徑
  • 從每個中間節點到 destination node 的最小成本路徑

主要問題 source node to destination node 的最小成本路徑就可以根據這些小問題的解來建構。

Approaches of Dynamic Programming

Top-Down Approach (Memoization)

從最後開始 recursive 拆分成更小的子問題，並將子問題的結果儲存在 memoization table 以避免重複計算。

Bottom-Up Approach (Tabulation)

從最小的子問題開始，逐步建立最終問題的解，由下而上的方式在表格中紀錄子問題的解答以避免重複計算。

Common Algorithms that Use Dynamic Programming

  • Longest Common Subsequence (LCS): 找兩字串的最長 common subsequence
  • Shortest Path in a Graph: 找 Graph 中兩點之間的最短路徑
  • Knapsack Problem 背包問題: 給定容量的背包，求可以放置的物品的最大值
  • Matrix Chain Multiplication: 優化矩陣乘法以最小的運算次數
  • Fibonacci Sequence: 費氏數列

Example

[Easy] 509. Fibonacci Number 費氏數列

Fibonacci Number

經典的費氏數列題型，這邊我們分別來看三種不同的解法：

  1. Recursive:

    1
    2
    3
    4
    def fib(n: int):
        if n <= 1:
            return n
        return fib(n-1) + fib(n-2)
    • 求 fib(5) 詳細過程
      • fib(4) + fib(3)
      • fib(3) + fib(2) + fib(3)
      • fib(2) + fib(1) + fib(2) + fib(3)
      • fib(1) + fib(0) + fib(1) + fib(2) + fib(3)
      • 1 + fib(0) + fib(1) + fib(2) + fib(3)
      • 1 + fib(1) + fib(2) + fib(3)
      • 2 + fib(2) + fib(3)
      • 2 + fib(1) + fib(0) + fib(3)
      • 3 + fib(0) + fib(3)
      • 3 + fib(3)
      • 3 + fib(2) + fib(1)
      • 3 + fib(1) + fib(0) + fib(1)
      • 4 + fib(0) + fib(1)
      • 4 + fib(1)
      • 5

  2. Top-down:

    1
    2
    3
    4
    5
    6
    7
    8
    def fib(n: int, result={}):
        if n <= 1:
            return n
        
        if n not in result:
            result[n] = fib(n-1, result) + fib(n-2, result)

        return result[n]
    • 求 fib(5)
      • fib(4) + fib(3)
      • fib(3) + fib(2) + fib(3)
      • fib(2) + fib(1) + fib(2) + fib(3)
      • fib(1) + fib(0) + fib(1) + fib(2) + fib(3)
      • 1 + fib(0) + fib(1) + fib(2) + fib(3)
      • 1 + fib(1) + fib(2) + fib(3)
      • 2 + fib(2) + fib(3) // fib(2) is already known
      • 3 + fib(3) // fib(3) is already known
      • 5

    Top-down 做法也是從最後開始計算，並且把計算結果儲存起來，這邊可以看到相比 recursive 的做法，少了幾次重複計算。

  3. Bottom-up:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    def fib(n: int):
        if n <=1 :
            return n
        
        dp = [0, 1] + [0] * (n-1)
        
        for i in range(2, n+1):
            dp[i] = dp[i-1] + dp[i-2]
        
        return dp[n]
    • 求 fib(5)
      • dp[2] = dp[1] + dp[0] = 1
      • dp[3] = dp[2] + dp[1] = 2
      • dp[4] = dp[3] + dp[2] = 3
      • dp[5] = dp[4] + dp[3] = 5

Related problem:

[Easy] 70. Climbing Stairs

You are climbing a staircase. It takes n steps to reach the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Thought:

  • n=1 (Answer: 1)
    • 1 step
  • n=2 (Answer: 2)
    • 1 step + 1 step
    • 2 steps
  • n=3 (Answer: 3)
    • 1 step + 1 step + 1 step
    • 1 step + 2 steps
    • 2 steps + 1 step
  • n=4 (Answer: 5)
    • 1 step + 1 step + 1 step + 1 step
    • 2 steps + 2 steps
    • 2 steps + 1 step + 1 step
    • 1 step + 2 steps + 1 step
    • 1 step + 1 step + 2 steps
  • n=5 (Answer: 8)
    • 1 step + 1 step + 1 step + 1 step + 1 step
    • 2 steps + 2 steps + 1 step
    • 2 steps + 1 step + 2 steps
    • 1 step + 2 steps + 2 steps
    • 2 steps + 1 step + 1 step + 1 step
    • 1 step + 2 steps + 1 step + 1 step
    • 1 step + 1 step + 2 steps + 1 step
    • 1 step + 1 step + 1 step + 2 steps

可以看出這題其實也是個費氏數列。

Related problem:

[Medium] 1143. Longest Common Subsequence

Given two strings text1 and text2, return the length of their longest common subsequence. If there is no common subsequence, return 0.

A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.

  • For example, "ace" is a subsequence of "abcde".

A common subsequence of two strings is a subsequence that is common to both strings.

這邊我們一樣先列出幾個範例，找規則（這題需要使用 2-D array):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# text1: abcde
# text2: ace

#   j 0 1 2 3
#       a c e
# i 
# 0   0 0 0 0
# 1 a 0 1 1 1
# 2 b 0 1 1 1
# 3 c 0 1 2 2
# 4 d 0 1 2 2
# 5 e 0 1 2 3

# Ans: 3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
# text1: abcba
# text2: abcbcba

#   j 0 1 2 3 4 5 6 7
#       a b c b c b a
# i 
# 0   0 0 0 0 0 0 0 0
# 1 a 0 1 1 1 1 1 1 1
# 2 b 0 1 2 2 2 2 2 2
# 3 c 0 1 2 3 3 3 3 3
# 4 b 0 1 2 3 4 4 4 4
# 5 a 0 1 2 3 4 4 4 5

# Ans: 5
  • 當 text1[i] == text2[j] 時，dp[i][j] = dp[i-1][j-1] + 1
  • Otherwise, dp[i][j] = max(dp[i-1][j], dp[i][j-1])

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        rows = len(text1)
        cols = len(text2)

        dp = [[0] * (cols+1) for _ in range(rows+1)]
        
        for i in range(1, rows+1):
            for j in range(1, cols+1):
                if text1[i-1] == text2[j-1]:
                    dp[i][j] = dp[i-1][j-1] + 1
                else:
                    dp[i][j] = max(dp[i][j-1], dp[i-1][j])

        return dp[rows][cols]

DP related problems: