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

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

什么最優(yōu)子結構

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

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

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

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

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

不是說有 3 個概念嗎！

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

2. 流程

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

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

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

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

2.1 是否存在子問題

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

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

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

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

那么原始問題就變成：

先分別求解路線 1 和路線 2上的最大值。路線 1的最大值為 3,路線 2上的最大值是8。
然后求解出路線 1和路線 2兩者之間的最大值 8。把求得的結果和出發(fā)點的數(shù)字 7 相加，7+8=15 就是最后答案。
只有 2 行時，兔子能獲得的最多蘿卜數(shù)為 15，肉眼便能看的出來。

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

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

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

路線 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。

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

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

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

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

使用二維數(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)
'''
輸出結果
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))
# 構建 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í)行程序后，久久沒有得到結果，甚至會超時。原因何在？如下圖：

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

**這便是重疊子問題！**子問題被重復計算。

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

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

怎么解決重疊子問題

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

這里使用字典作為緩存器，以子問題的起始位置為關鍵字，以子問題的結果為值。

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():
        # 檢查緩存中是否存在子問題的結果
        left_max = dic[i + 1, j]
    else:
        # 緩存中沒有，才遞歸求解
        left_max = get_max_lb(i + 1, j)
        # 求解后的結果緩存起來
        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ù)，每次運行結果不一樣。但是，每次運行后的速度是非常給力的。

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

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

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

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

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

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

從已知找到未知。

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

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

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

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

2.3 狀態(tài)轉移

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

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

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

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

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

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

有了上述的這張表，就可以使用動態(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)轉移表中
            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)
'''
輸出結果：
[[4, 5, 2, 6, 5], [7, 12, 10, 10], [20, 13, 12], [23, 21], [30]]
'''

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

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

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

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

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

在狀態(tài)轉移過程中，我們僅關心當前得到的狀態(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ù)，準備保存最新的狀態(tài)數(shù)據(jù)
    dp.clear()
    for j in range(len(nums[i])):
        if i == len(nums) - 1:
            # 最后一行緩存于狀態(tài)轉移表中
            dp.append(nums[i][j])
        else:
            dp.append(nums[i][j] + max(tmp[j], tmp[j + 1]))
print(dp)
'''
輸出結果：
[30]
'''