動(dòng)態(tài)規(guī)劃（Dynamic Programming，簡稱 DP）是一種在數(shù)學(xué)、計(jì)算機(jī)科學(xué)和經(jīng)濟(jì)學(xué)中使用的，通過把原問題分解為相對簡單的子問題的方式來求解復(fù)雜問題的方法。動(dòng)態(tài)規(guī)劃常常適用于有重疊子問題和最優(yōu)子結(jié)構(gòu)性質(zhì)的問題。
工作原理：
動(dòng)態(tài)規(guī)劃的工作原理基于兩個(gè)核心概念：
- 重疊子問題：在求解問題的過程中，有些子問題可能會(huì)被重復(fù)計(jì)算多次。動(dòng)態(tài)規(guī)劃通過保存子問題的解，避免了這些重復(fù)計(jì)算。
- 最優(yōu)子結(jié)構(gòu)：如果問題的最優(yōu)解可以由其子問題的最優(yōu)解有效地構(gòu)造出來，那么該問題就具有最優(yōu)子結(jié)構(gòu)性質(zhì)。
動(dòng)態(tài)規(guī)劃通常包含以下步驟：
- 定義狀態(tài)：描述問題的子結(jié)構(gòu)，即子問題的解。
- 狀態(tài)轉(zhuǎn)移方程：描述如何從子問題的解構(gòu)造出原問題的解。
- 初始化：為最小的子問題設(shè)置初始值。
- 計(jì)算：按照某種順序（通常是從最小子問題到最大子問題）計(jì)算所有子問題的解。
- 構(gòu)造解：使用計(jì)算出的子問題的解來構(gòu)造原問題的解。
實(shí)現(xiàn)方式：
動(dòng)態(tài)規(guī)劃的實(shí)現(xiàn)方式通常包括自底向上和帶備忘錄的自頂向下兩種。
- 自底向上：從最小的子問題開始，逐步計(jì)算更大子問題的解，直到求解出原問題的解。這種方式通常使用表格或數(shù)組來保存子問題的解。
- 帶備忘錄的自頂向下：從原問題開始，遞歸地求解子問題，并在求解過程中將子問題的解保存在備忘錄中，以避免重復(fù)計(jì)算。
應(yīng)用場景：
動(dòng)態(tài)規(guī)劃在許多領(lǐng)域都有廣泛的應(yīng)用，包括背包問題、最短路徑問題、最長公共子序列問題、編輯距離問題、資源分配問題等。
代碼實(shí)例：
以經(jīng)典的0-1背包問題為例，下面是使用動(dòng)態(tài)規(guī)劃求解0-1背包問題的Python代碼：
python復(fù)制代碼
def knapsack(values, weights, capacity): |
|
n = len(values) |
|
dp = [[0 for _ in range(capacity + 1)] for _ in range(n + 1)] |
|
for i in range(1, n + 1): |
|
for w in range(1, capacity + 1): |
|
if weights[i - 1] <= w: |
|
dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1]) |
|
else: |
|
dp[i][w] = dp[i - 1][w] |
|
return dp[n][capacity] |
|
# 示例 |
|
values = [60, 100, 120] |
|
weights = [10, 20, 30] |
|
capacity = 50 |
|
print(knapsack(values, weights, capacity)) # 輸出：220 |
在這個(gè)例子中，values數(shù)組表示每個(gè)物品的價(jià)值，weights數(shù)組表示每個(gè)物品的重量，capacity表示背包的容量。dp[i][w]表示考慮前i個(gè)物品，在背包容量為w的情況下能夠得到的最大價(jià)值。通過填充這個(gè)二維數(shù)組，我們可以得到原問題的解。
帶備忘錄的自底向上方法以及代碼實(shí)例
帶備忘錄的自底向上方法結(jié)合了自底向上和遞歸兩種策略。它首先通過遞歸地求解子問題來構(gòu)建問題的解空間，但為了避免重復(fù)計(jì)算，它使用一個(gè)“備忘錄”或稱為“查找表”來存儲(chǔ)已經(jīng)計(jì)算過的子問題的解。這樣，當(dāng)再次遇到相同的子問題時(shí)，可以直接從備忘錄中查找結(jié)果，而不是重新計(jì)算。
這種方法的優(yōu)勢在于它結(jié)合了遞歸的清晰性和自底向上的效率。遞歸使得代碼更易于理解和編寫，而備忘錄則確保了計(jì)算的高效性，避免了不必要的重復(fù)工作。
下面是一個(gè)使用帶備忘錄的自底向上方法解決0-1背包問題的Python代碼實(shí)例：
python復(fù)制代碼
def knapsack_memoization(values, weights, capacity): |
|
memo = [[None] * (capacity + 1) for _ in range(len(values) + 1)] |
|
def dp(i, w): |
|
# 如果當(dāng)前子問題的解已經(jīng)在備忘錄中，則直接返回 |
|
if memo[i][w] is not None: |
|
return memo[i][w] |
|
# 遞歸的基本情況 |
|
if i == 0 or w == 0: |
|
return 0 |
|
# 如果當(dāng)前物品重量大于背包容量，則不考慮該物品 |
|
if weights[i - 1] > w: |
|
memo[i][w] = dp(i - 1, w) |
|
else: |
|
# 否則，考慮選擇當(dāng)前物品或不選擇當(dāng)前物品兩種情況中的較大值 |
|
memo[i][w] = max(dp(i - 1, w), values[i - 1] + dp(i - 1, w - weights[i - 1])) |
|
return memo[i][w] |
|
# 調(diào)用遞歸函數(shù)，求解原問題 |
|
return dp(len(values), capacity) |
|
# 示例 |
|
values = [60, 100, 120] |
|
weights = [10, 20, 30] |
|
capacity = 50 |
|
print(knapsack_memoization(values, weights, capacity)) # 輸出：220 |
在這個(gè)例子中，memo數(shù)組就是我們的備忘錄，用于存儲(chǔ)子問題的解。dp函數(shù)是一個(gè)遞歸函數(shù)，它首先檢查備忘錄中是否已經(jīng)存在當(dāng)前子問題的解。如果存在，則直接返回該解；如果不存在，則遞歸地計(jì)算子問題的解，并將結(jié)果存儲(chǔ)在備忘錄中。這樣，當(dāng)相同的子問題再次被調(diào)用時(shí)，就可以直接從備忘錄中取得結(jié)果，避免重復(fù)計(jì)算。文章來源：http://www.zghlxwxcb.cn/news/detail-848841.html
注意，雖然這種方法在概念上使用了遞歸，但實(shí)際上它是通過自底向上的方式填充備忘錄的，因此避免了遞歸的深度限制，并且在實(shí)際執(zhí)行時(shí)通常比純遞歸方法更高效。文章來源地址http://www.zghlxwxcb.cn/news/detail-848841.html
到了這里，關(guān)于動(dòng)態(tài)規(guī)劃的工作原理，實(shí)現(xiàn)方式，應(yīng)用場景的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
