動態規劃也是一種演算法設計模式，常用來解決最佳化問題。它的方法是將問題(通常是遞迴地)分解成子問題，再以子問題的最佳解組成原問題的最佳解。

這樣的描述看起來完全就是前面提到的分治法+貪婪演算法，不過動態規劃比較特別的一點在於它會儲存運算過的子問題解，就可以不用重複運算，也可以將一些運算繁複的問題簡化。

因此動態規劃適合解決的問題有以下特性：

1. 有最佳子結構(optimal substructure)，也就是可以以子問題最佳解推得原問題最佳解(這部份跟貪婪演算法一樣)。
2. 有重疊子問題(overlapping subproblems)，意思是相同的子問題會在運算中反覆出現(最佳組合或組合種類等問題)。

背包問題

舉例來說，以貪婪演算法未必會得到最佳解的背包問題(knapsack problem)，就可以以動態規劃解決。背包問題是在一組已知重量及價值的物品中，要找出背包可容納的重量範圍內，價值最高的物品組合。

如果以暴力方法解決，就要運算所有的組合，例如當有三樣物品A, B, C時，就必須計算A, B, C, A+B, B+C, A+C, A+B+C等所有可能組合，再比較在重量限制內哪一組合的價值最高。這樣的方式會反覆運算同樣的內容，速度非常慢。

以動態規劃解決的話，就會從子問題開始，記錄並持續更新最佳解。例如在每樣物品最多只能拿一個的情況下，要知道容量三公斤背包裝得下的最佳組合，可以記錄成類似下面的表格：

從第一列開始，以物品A來說，一、二、三公斤的背包都容納得下，所以所有容量的當前最佳解都是$500。

第二列，以物品B來說，一公斤背包裝不下，最佳解仍為原本的$500；兩公斤背包裝得下，更新當前最佳解為$1000；三公斤裝得下，且裝完後還剩下一公斤空間，而我們已記錄一公斤的最佳解為$500，所以加起來更新為$1500。

第三列，以物品C來說，一、二公斤的背包都裝不下，最佳解維持不變；三公斤背包裝得下，但價值並沒有超過當前最佳的$1500，所以不更新。

也就是說，動態規劃先找出一個物品在各容量背包中的最佳解，並記錄下來，接下來如果有別的物品+剩餘空間可裝物品是更好的組合，就更新記錄，而過程中已經計算過的物品不必再次運算。

費氏數列

以費氏數列也可以看動態規劃的例子。

費氏數列的開頭為0, 1 ，後面的數字都為其前兩個數字相加，例如數列的前面幾個數字為：0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55....

也可以說，除了開頭的F0 = 0, F1 = 1之外，數列中的第n個數字Fn，可以寫成 Fn = Fn-1 + Fn-2。

如果我們想要寫一個函式Fibonacci(n)，在輸入n時回傳費氏數列中第n個數字(例如Fibonacci(6)回傳8)，最簡單的作法可以用遞迴。可以從以下的程式碼看到，每一次呼叫Fibonacci(n)，裡面會再呼叫Fibonacci(n-1)+Fibonacci(n-2)，兩個函式又會再各自呼叫Fibonacci(n-1)+Fibonacci(n-2)...，這樣的做法效率很差，而且一直在做一樣的計算。

資料來源：Geeksforgeeks

# Function for nth Fibonacci number
 
def Fibonacci(n):
    if n<0:
        print("Incorrect input")
    # First Fibonacci number is 0
    elif n==0:
        return 0
    # Second Fibonacci number is 1
    elif n==1:
        return 1
    else:
        return Fibonacci(n-1)+Fibonacci(n-2)
 
# Driver Program
 
print(Fibonacci(9))
 
#This code is contributed by Saket Modi

如果是動態規劃的想法，則是每次將已經算過的數字記錄下來，就可以避免上例中的重複計算。例如下方的寫法就是將計算過的數字存在陣列中。

# Fibonacci Series using Dynamic Programming
def fibonacci(n):
     
    # Taking 1st two fibonacci numbers as 0 and 1
    f = [0, 1]
     
     
    for i in range(2, n+1):
        f.append(f[i-1] + f[i-2])
    return f[n]
     
print(fibonacci(9))

由上面兩個不太一樣的問題，可以發現動態規劃並非只有一種將問題分解成子問題的方式，有時候需要很多的思考和設計來找到合適的解法。

另外，除了避免重複運算、增進效率外，動態規劃會記錄子問題解這點，也顯示出跟貪婪演算法的一大差異：貪婪演算法是每一步作出當前最佳解，持續把問題縮小，也就不會再回頭修改已經作的決定；動態規劃則是每一步都是基於前面已得出的子問題解來進行，並可能會更新已得到的答案。