動態規劃 ·

演算法與解題 - 系列文

11: ➫

11: 本節課介紹動態規劃與其解決具有最優子結構的複雜問題。

動態規劃的介紹
#

動態規劃是一種算法思想，用於解決具有最優子結構的複雜問題。它涉及多輪決策，將大問題分解為互相依賴的小問題，並逐步求解。

動態規劃與分治法的區別
#

相同點：都將大問題分解為小問題，逐步解決。
不同點：分治法的子問題相互獨立，而動態規劃的子問題不獨立，相互依賴。

動態規劃的核心概念
#

最優子結構：問題的最優解包含子問題的最優解。
狀態：描述問題解決過程中的某個階段。
決策：每階段的選擇。
狀態轉移方程：描述狀態之間的轉移關係。
目標：定義最終求解的目標。
終止條件：決定算法結束的條件。

動態規劃的方法論
#

分階段：確定問題的不同階段。
找狀態：確定每階段的狀態。
做決策：在每階段做出選擇。
建立狀態轉移方程：確定各階段狀態之間的關係。
定目標：明確最終求解的目標。
尋找終止條件：設定算法終止的條件。

動態規劃的案例
#

最長公共子序列 (Longest Common Subsequence, LCS) 給定兩個序列 X = {x1, x2, …, xm} 和 Y = {y1, y2, …, yn}，找出 X 和 Y 長度最長的公共子序列。公共子序列的意思是，序列中的元素可以不連續，但必須保持它們在原序列中的順序。

Go 語言實現
#

在 Go 語言中，我們可以使用二維陣列來儲存中間結果，以達到動態規劃的目的。

package main

import (
    "fmt"
)

// LongestCommonSubsequence 函數計算兩個字符串的最長公共子序列的長度
func LongestCommonSubsequence(X, Y string) int {
    m := len(X)
    n := len(Y)

    // 創建一個二維切片來儲存子問題的解
    dp := make([][]int, m+1)
    for i := range dp {
        dp[i] = make([]int, n+1)
    }

    // 填充 dp 切片
    for i := 0; i <= m; i++ {
        for j := 0; j <= n; j++ {
            if i == 0 || j == 0 {
                dp[i][j] = 0
            } else if X[i-1] == Y[j-1] {
                dp[i][j] = dp[i-1][j-1] + 1
            } else {
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
            }
        }
    }
    return dp[m][n] // 返回整個序列的最長公共子序列的長度
}

// max 函數返回兩個整數中的較大值
func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func main() {
    X := "AGGTAB"
    Y := "GXTXAYB"
    fmt.Println("Length of Longest Common Subsequence is", LongestCommonSubsequence(X, Y))
}

在這段 Go 程式碼中，我們使用了一個名為 LongestCommonSubsequence 的函數來計算兩個字符串的最長公共子序列的長度。該函數使用了動態規劃的方法，通過創建一個二維陣列（dp），並遞增地填充它來找出最長公共子序列的長度。最後，從 dp[m][n] 獲取整個序列的最長公共子序列的長度。