動態規劃(Dynamic programming)，將複雜的問題分解成較為簡單的子問題來處理，在處理子問題的過程中可以尋找其中的規律，並將每一次的結果都進行計算儲存，依序從簡單到困難的問題逐一解決，可以在動態規劃進行遞迴的過程中減少處理相同問題的時間。

範例說明 :
題目 : 你有一個背包，最大的承重為W，有n種物品，每種物品i的重量為w[i]，價值為v[i]。假設背包承重W = 7 、物品重量 n = 4、物品的重量 w = [1, 3 , 4, 5]、物品的價值 v = [1, 4, 5, 7]，如何在不超過承重的狀況下，將背包內物品的總價值最大化。

Step 1 : 設定dp[j]，表示容量為j時的最大價值

Step 2 : 設dp[0] = 0，其餘的dp[j]初始化為0

Step 3 : 狀態轉移

對於每個物品i ( 從 0 到 n-1 );

從後向前更新背包容量j ( 從 W 到 [i] );

dp[ j ] = max(dp[ j ], dp[ j - weights [ i ] ] + values[ i ]);

Step 4 : 根據題目範例，得出選擇的物品2(重量 = 3、價值 = 4)和物品3(重量 = 4、價值 = 5)，總重量 = 7，總價值 = 9。

程式碼 :

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int knapsack(int W, const vector<int>& weights, const vector<int>& values) {
    int n = weights.size();
    vector<int> dp(W + 1, 0);
    
    for (int i = 0; i < n; ++i) {
        for (int j = W; j >= weights[i]; --j) {
            dp[j] = max(dp[j], dp[j - weights[i]] + values[i]);
        }
    }
    
    return dp[W];
}

int main() {
    int W = 7;  // 背包容量
    vector<int> weights = {1, 3, 4, 5};  // 物品重量
    vector<int> values = {1, 4, 5, 7};    // 物品價值
    
    int max_value = knapsack(W, weights, values);
    cout << "最大價值: " << max_value << endl;

    return 0;
}

優點 :

1. 可以避免重複計算，提高計算效率
2. 透過狀態轉移將問題利用較為簡單的方式進行描述

缺點 :

1. 需要儲存計算過程中的結果，占用的空間較大
2. 可能會多計算無用的子問題