1. 概述

動態(tài)規(guī)劃算法應(yīng)用非常之廣泛。

對于算法學(xué)習(xí)者而言，不跨過動態(tài)規(guī)劃這道門，不算真正了解算法。

初接觸動態(tài)規(guī)劃者，理解其思想精髓會存在一定的難度，本文將通過一個案例，抽絲剝繭般和大家聊聊動態(tài)規(guī)劃。

動態(tài)規(guī)劃算法有 3 個重要的概念：

• 重疊子問題。
• 最優(yōu)子結(jié)構(gòu)。
• 狀態(tài)轉(zhuǎn)移。

只有吃透這 3 個概念，才叫真正理解什么是動態(tài)規(guī)劃。

什么是重疊子問題

動態(tài)規(guī)劃和分治算法有一個相似之處。

將原問題分解成相似的子問題，在求解的過程中通過子問題的解求出原問題的解。

動態(tài)規(guī)劃與分治算法的區(qū)別

• 分治算法的每一個子問題具有完全獨立性，只會被計算一次。
• 二分查找是典型的分治算法實現(xiàn)，其子問題是把數(shù)列縮小后再二分查找，每一個子問題只會被計算一次。
• 動態(tài)規(guī)劃經(jīng)分解得到的子問題往往不是互相獨立的，有些子問題會被重復(fù)計算多次，這便是重疊子問題。
• 同一個子問題被計算多次，完全是沒有必要的，可以緩存已經(jīng)計算過的子問題，再次需要子問題結(jié)果時只需要從緩存中獲取便可。這便是動態(tài)規(guī)劃中的典型操作，優(yōu)化重疊子問題，通過空間換時間的優(yōu)化手段提高性能。

重疊子問題并不是動態(tài)規(guī)劃的專利，重疊子問題是一個很普見的現(xiàn)象。

什么最優(yōu)子結(jié)構(gòu)

最優(yōu)子結(jié)構(gòu)是動態(tài)規(guī)劃的必要條件。因為動態(tài)規(guī)劃只能應(yīng)用于具有最優(yōu)子結(jié)構(gòu)的問題，在解決一個原始問題時，是否能套用動態(tài)規(guī)劃算法，分析是否存在最優(yōu)子結(jié)構(gòu)是關(guān)鍵。

那么！到底什么是最優(yōu)子結(jié)構(gòu)？概念其實很簡單，局部最優(yōu)解能決定全局最優(yōu)解。

如拔河比賽中。如果 A隊中的每一名成員的力氣都是每一個班上最大的，由他們組成的拔河隊毫無疑問，一定是也是所有拔河隊中實力最強的。

如果把求解哪一個團隊的力量最大當(dāng)成原始問題，則每一個人的力量是否最大就是子問題，則子問題的最優(yōu)決定了原始問題的最優(yōu)。

所以，動態(tài)規(guī)劃多用于求最值的應(yīng)用場景。

不是說有 3 個概念嗎！

不急，先把狀態(tài)轉(zhuǎn)移這個概念放一放，稍后再解釋。

2. 流程

下面以一個案例的解決過程描述使用動態(tài)規(guī)劃的流程。

問題描述：小兔子的難題。

有一只小兔子站在一片三角形的胡蘿卜地的入口，如下圖所示，圖中的數(shù)字表示每一個坑中胡蘿卜的數(shù)量，小兔子每次只能跳到左下角或者右下角的坑中，請問小兔子怎么跳才能得到最多數(shù)量的胡蘿卜？

首先這個問題是求最值問題， 是否能夠使用動態(tài)規(guī)劃求解，則需要一步一步分析，看是否有滿足使用動態(tài)規(guī)劃的條件。

2.1 是否存在子問題

先來一個分治思想：思考或觀察是否能把原始問題分解成相似的子問題，把解決問題的希望寄托在子問題上。

那么，針對上述三角形數(shù)列，是否存在子問題？

現(xiàn)在從數(shù)字7出發(fā)，兔子有 2 條可行路線。

為了便于理解，首先模糊第 3 行后面的數(shù)字或假設(shè)第 3行之后根本不存在。

那么原始問題就變成：

• 先分別求解路線 1 和路線 2上的最大值。路線 1的最大值為 3,路線 2上的最大值是8。
• 然后求解出路線 1和路線 2兩者之間的最大值 8。 把求得的結(jié)果和出發(fā)點的數(shù)字 7 相加，7+8=15 就是最后答案。

• 只有 2 行時，兔子能獲得的最多蘿卜數(shù)為 15，肉眼便能看的出來。

前面是假設(shè)第 3 行之后都不存在，現(xiàn)在把第 3 行放開，則路線 1 路線2的最大值就要發(fā)生變化，但是，對于原始問題來講，可以不用關(guān)心路線 1 和路線 2 是怎么獲取到最大值，交給子問題自己處理就可以了。

反正，到時從路線 1 和路線 2 的結(jié)果中再選擇一個最大值就是。

把第 3 行放開后，路線 1 就要重新更新最大值，如上圖所示，路線 1也可以分解成子問題，分解后，也只需要關(guān)心子問題的返回結(jié)果。

• 路線 1 的子問題有 2個，路線 1_1和路線1_2。求解 2 個子問題的最大值后，再在 2 個子問題中選擇最大值8，最后路線 1的最大值為3+8=11。
• 路線 2 的子問題有 2個，路線 2_1和路線2_2。求解 2 個子問題的最大值后，再在 2 個子問題中選擇最大值2，最后路線 2的最大值為8+2=10。

當(dāng)?shù)?3 行放開后，更新路線 1和路線2的最大值，對于原始問題而言，它只需要再在 2 個子問題中選擇最大值 11，最終問題的解為7+11=18。

如果放開第 4 行，將重演上述的過程。和原始問題一樣，都是從一個點出發(fā)，求解此點到目標(biāo)行的最大值。所以說，此問題是存在子問題的。

并且，只要找到子問題的最優(yōu)解，就能得到最終原始問題的最優(yōu)解。不僅存在子問題，而且存在最優(yōu)子結(jié)構(gòu)。

顯然，這很符合遞歸套路：遞進給子問題，回溯子問題的結(jié)果。

• 使用二維數(shù)列表保存三角形數(shù)列中的所有數(shù)據(jù)。a=[[7],[3,8],[8,1,2],[2,7,4,4],[4,5,2,6,5]]。
• 原始問題為 f(0，0)從數(shù)列的(0,0)出發(fā)，向左下角和右下角前行，一直找到此路徑上的數(shù)字相加為最大。

• f(0,0)表示以第 1 行的第 1 列數(shù)字為起始點。

• 分解原始問題 f(0,0)=a(0,0)+max(f(1,0)+f(1,1))。
• 因為每一個子問題又可以分解，讓表達式更通用 f(i,j)=a(i,j)+max(f(i+1,j)+f(i+1,j+1))。

• (i+1,j)表示 (i,j)的左下角，(i+1,j+1)表示 (i,j)的右下角，

編碼實現(xiàn)：

# 已經(jīng)數(shù)列
nums = [[7], [3, 8], [8, 1, 2], [2, 7, 4, 4], [4, 5, 2, 6, 5]]
# 遞歸函數(shù)
def get_max_lb(i, j):
    if i == len(nums) - 1:
        # 遞歸出口
        return nums[i][j]
    # 分解子問題
    return nums[i][j] + max(get_max_lb(i + 1, j), get_max_lb(i + 1, j + 1))
# 測試
res = get_max_lb(0, 0)
print(res)
'''
輸出結(jié)果
30
'''

不是說要聊聊動態(tài)規(guī)劃的流程嗎！怎么跑到遞歸上去了。

其實所有能套用動態(tài)規(guī)劃的算法題，都可以使用遞歸實現(xiàn)，因遞歸平時接觸多，從遞歸切入，可能更容易理解。

2.2 是否存在重疊子問題

先做一個實驗，增加三角形數(shù)的行數(shù)，也就是延長路徑線。

import random
nums = []
# 遞歸函數(shù)
def get_max_lb(i, j):
    if i == len(nums) - 1:
        return nums[i][j]
    return nums[i][j] + max(get_max_lb(i + 1, j), get_max_lb(i + 1, j + 1))
# 構(gòu)建 100 行的二維列表
for i in range(100):
    nums.append([])
    for j in range(i + 1):
        nums[i].append(random.randint(1, 100))
res = get_max_lb(0, 0)
print(res)

執(zhí)行程序后，久久沒有得到結(jié)果，甚至?xí)瑫r。原因何在？如下圖：

路線1_2和路線2_1的起點都是從同一個地方（藍色標(biāo)注的位置）出發(fā)。顯然，從數(shù)字 1（藍色標(biāo)注的數(shù)字）出發(fā)的這條路徑會被計算 2 次。在上圖中被重復(fù)計算的子路徑可不止一條。

**這便是重疊子問題！**子問題被重復(fù)計算。

當(dāng)三角形數(shù)列的數(shù)據(jù)不是很多時，重復(fù)計算對整個程序的性能的影響微不足道 。如果數(shù)據(jù)很多時，大量的重復(fù)計算會讓計算機性能低下，并可能導(dǎo)致最后崩潰。

因為使用遞歸的時間復(fù)雜度為O(2^n)。當(dāng)數(shù)據(jù)的行數(shù)變多時，可想而知，性能有多低下。

怎么解決重疊子問題

答案是：使用緩存，把曾經(jīng)計算過的子問題結(jié)果緩存起來，當(dāng)再次需要子問題結(jié)果時，直接從緩存中獲取，就沒有必要再次計算。

這里使用字典作為緩存器，以子問題的起始位置為關(guān)鍵字，以子問題的結(jié)果為值。

import random
def get_max_lb(i, j):
    if i == len(nums) - 1:
        return nums[i][j]
    left_max = None
    right_max = None
    if (i + 1, j) in dic.keys():
        # 檢查緩存中是否存在子問題的結(jié)果
        left_max = dic[i + 1, j]
    else:
        # 緩存中沒有，才遞歸求解
        left_max = get_max_lb(i + 1, j)
        # 求解后的結(jié)果緩存起來
        dic[(i + 1, j)] = left_max
    if (i + 1, j + 1) in dic.keys():
        right_max = dic[i + 1, j + 1]
    else:
        right_max = get_max_lb(i + 1, j + 1)
        dic[(i + 1, j + 1)] = right_max
    return nums[i][j] + max(left_max, right_max)
# 已經(jīng)數(shù)列
nums = []
# 緩存器
dic = {}
for i in range(100):
    nums.append([])
    for j in range(i + 1):
        nums[i].append(random.randint(1, 100))
# 遞歸調(diào)用
res = get_max_lb(0, 0)
print(res)

因使用隨機數(shù)生成數(shù)據(jù)，每次運行結(jié)果不一樣。但是，每次運行后的速度是非常給力的。

當(dāng)出現(xiàn)重疊子問題時，可以緩存曾經(jīng)計算過的子問題。

好 ！現(xiàn)在到了關(guān)鍵時刻，屏住呼吸，從分析緩存中的數(shù)據(jù)開始。

使用遞歸解決問題，從結(jié)構(gòu)上可以看出是從上向下的一種處理機制。所謂從上向下，也就是由原始問題開始一路去尋找答案。從本題來講，就是從第一行一直找到最后一行，或者說從未知找到``已知`。

根據(jù)遞歸的特點，可知緩存數(shù)據(jù)的操作是在回溯過程中發(fā)生的。

當(dāng)再次需要調(diào)用某一個子問題時，這時才有可能從緩存中獲取到已經(jīng)計算出來的結(jié)果。緩存中的數(shù)據(jù)是每一個子問題的結(jié)果，如果知道了某一個子問題，就可以通過子問題計算出父問題。

這時，可能就會有一個想法？

從已知找到未知。

任何一條路徑只有到達最后一行后才能知道最后的結(jié)果?？梢哉J(rèn)為，最后一行是已知數(shù)據(jù)。先緩存最后一行，那么倒數(shù)第 2 行每一個位置到最后一行的路徑的最大值就可以直接求出來。

同理，知道了倒數(shù)第 2 行的每一個位置的路徑最大值，就可以求解出倒數(shù)第 3行每一個位置上的最大值。以此類推一直到第 1 行。

天呀！多完美，還用什么遞歸。

可以認(rèn)為這種思想便是動態(tài)規(guī)劃的核心：自下向上。

2.3 狀態(tài)轉(zhuǎn)移

還差最后一步，就能把前面的遞歸轉(zhuǎn)換成動態(tài)規(guī)劃實現(xiàn)。

什么是狀態(tài)轉(zhuǎn)移？

前面分析從最后 1 開始求最大值過程，是不是有點像田徑場上的多人接力賽跑，第 1 名運動力爭跑第 1，把狀態(tài)轉(zhuǎn)移給第 2名運動員，第 2名運動員持續(xù)保持第 1，然后把狀態(tài)轉(zhuǎn)移給第 3運動員，第 3名運動員也保持他這一圈的第 1，一至到最后一名運動員，都保持自己所在那一圈中的第 1。很顯然最后結(jié)果，他們這個團隊一定是第 1名。

把子問題的值傳遞給另一個子問題，這便是狀態(tài)轉(zhuǎn)移。當(dāng)然在轉(zhuǎn)移過程中，一定會存在一個表達式，用來計算如何轉(zhuǎn)移。

用來保存每一個子問題狀態(tài)的表稱為 dp 表，其實就是前面遞歸中的緩存器。

用來計算如何轉(zhuǎn)移的表達式，稱為狀態(tài)轉(zhuǎn)移方程式。

有了上述的這張表，就可以使用動態(tài)規(guī)劃自下向上的方式解決“兔子的難題”這個問題。

nums = [[7], [3, 8], [8, 1, 2], [2, 7, 4, 4], [4, 5, 2, 6, 5]]
# dp列表
dp = []
idx = 0
# 從最后一行開始
for i in range(len(nums) - 1, -1, -1):
    dp.append([])
    for j in range(len(nums[i])):
        if i == len(nums) - 1:
            # 最后一行緩存于狀態(tài)轉(zhuǎn)移表中
            dp[idx].append(nums[i][j])
        else:
            dp[idx].append(nums[i][j] + max(dp[idx - 1][j], dp[idx - 1][j + 1]))
    idx += 1
print(dp)
'''
輸出結(jié)果：
[[4, 5, 2, 6, 5], [7, 12, 10, 10], [20, 13, 12], [23, 21], [30]]
'''

程序運行后，最終輸出結(jié)果和前面手工繪制的dp表中的數(shù)據(jù)一模一樣。

其實動態(tài)規(guī)劃實現(xiàn)是前面遞歸操作的逆過程。時間復(fù)雜度是O(n^2)。

并不是所有的遞歸操作都可以使用動態(tài)規(guī)劃進行逆操作，只有符合動態(tài)規(guī)劃條件的遞歸操作才可以。

上述解決問題時，使用了一個二維列表充當(dāng)dp表，并保存所有的中間信息。

思考一下，真的有必要保存所有的中間信息嗎？

在狀態(tài)轉(zhuǎn)移過程中，我們僅關(guān)心當(dāng)前得到的狀態(tài)信息，曾經(jīng)的狀態(tài)信息其實完全可以不用保存。

所以，上述程序完全可以使用一個一維列表來存儲狀態(tài)信息。

nums = [[7], [3, 8], [8, 1, 2], [2, 7, 4, 4], [4, 5, 2, 6, 5]]
# dp表
dp = []
# 臨時表
tmp = []
# 從最后一行開始
for i in range(len(nums) - 1, -1, -1):
    # 把上一步得到的狀態(tài)數(shù)據(jù)提出來
    tmp = dp.copy()
    # 清除 dp 表中原來的數(shù)據(jù)，準(zhǔn)備保存最新的狀態(tài)數(shù)據(jù)
    dp.clear()
    for j in range(len(nums[i])):
        if i == len(nums) - 1:
            # 最后一行緩存于狀態(tài)轉(zhuǎn)移表中
            dp.append(nums[i][j])
        else:
            dp.append(nums[i][j] + max(tmp[j], tmp[j + 1]))
print(dp)
'''
輸出結(jié)果：
[30]
'''

3.總結(jié)

動態(tài)規(guī)劃問題一般都可以使用遞歸實現(xiàn)，遞歸是一種自上向下的解決方案，而動態(tài)規(guī)劃是自下向上的解決方案，兩者在解決同一個問題時的思考角度不一樣，但本質(zhì)是一樣的。

并不是所有的遞歸操作都能轉(zhuǎn)換成動態(tài)規(guī)劃，是否能使用動態(tài)規(guī)劃算法，則需要原始問題符合最優(yōu)子結(jié)構(gòu)和重疊子問題這 2 個條件。在使用動態(tài)規(guī)劃過程中，找到狀態(tài)轉(zhuǎn)移表達式是關(guān)鍵。

以上就是Python算法思想集結(jié)深入理解動態(tài)規(guī)劃的詳細內(nèi)容，更多關(guān)于Python算法動態(tài)規(guī)劃的資料請關(guān)注腳本之家其它相關(guān)文章！

最新評論