动态规划（Dynamic Programming, DP）是一种通过分解问题为子问题、存储子问题解并重复利用的算法技巧。

斐波那契数列

先从斐波那契数列问题开始，这个看上去最容易理解。
斐波那契数列定义为：

$$ F(n) = F(n-1) + F(n-2) $$

且 $ F(0) = 0, F(1) = 1$。求第$n$个斐波那契数。

cpp


//递归版本
int fibonacci(int n)
{
    if ( n <= 1 )
        return n;
    else
        return fibonacci(n-1) + fibonacci(n-2);
}

//动态规划版本
int fibonacci_dp(int n)
{
    if ( n <= 1 )
        return n;
    vector<int> dp(n+1, 0);
    dp[0] = 0;
    dp[1] = 1;
    for ( int i = 2; i <= n; i++ )
        dp[i] = dp[i-1] + dp[i-2];
    return dp[n];
}

可以看出，动态规划版本比递归版快很多。动态规划版本的思想是自底向上。

爬楼梯问题

给定一楼梯共n个台阶，每次可以上1或2个台阶，求有多少种方案可以爬到顶楼。
解析：例如，假设有3个台阶，那么有3种爬楼梯的方案：1+1+1，1+2，2+1。

下面的代码分别展示了回溯、暴力穷举、自顶向下的动态规划、自底向上的动态规划以及滚动数组法的实现。

cpp


#include <iostream>
#include <vector>
using namespace std;

// 方案一：回溯法，递归，最直观
void backtrack(int n, int state, vector<int>& choices, int& res)
{
    if (state == n)
    {
        res ++;
    }
    for (auto &choice : choices)
    {
        if (state + choice <= n)
        {
            backtrack(n, state + choice, choices, res);
        }
    }
}

int climbStairsBacktrack(int n)
{
    vector<int> choices = {1, 2};
    int state =0;
    int res = 0;
    backtrack(n, state, choices, res);
    return res;
}


// 方案二
// 暴力穷举法
// 时间复杂度O(2^n)
int climbStairs(int n)
{
    if (n == 1)
        return 1;
    if (n == 2)
        return 2;

    // 要么爬到n-1，要么爬到n-2
    return climbStairs(n - 1) + climbStairs(n - 2);
}

// 方案三：带备忘录的自顶向下法 
// top-down with memoization
// 对上面暴力穷举的优化，希望将所有重叠的子问题都只被计算一次
int climbStairs_tdm(int n, vector<int>& memo)
{
    if (n <= 2)
        return n;
    if (memo[n] != -1)
        return memo[n];
    memo[n] = climbStairs_tdm(n - 1, memo) + climbStairs_tdm(n - 2, memo);
    return memo[n];
}

int climbStairs_tdm(int n)
{
    vector<int> memo(n+1, -1);
    return climbStairs_tdm(n, memo);
}

// 方案四：动态规划，自底向上法
// bottom-up method
int climbStairs_DP(int n)
{
    if (n <= 2)
        return n;
    vector<int> dp(n+1, 0);
    //初始化初始状态
    dp[1] = 1;
    dp[2] = 2;
    //状态转移方程
    for (int i = 3; i <= n; i++)
    {
        dp[i] = dp[i-1] + dp[i-2];
    }
    return dp[n];
}

// 对自底向上法的空间优化
int climbStairs_DP_space(int n)
{
    if (n <= 2)
        return n;
    int prev1 = 1;
    int prev2 = 2;
    int curr = 0;
    //省去了dp数组，只用了两个变量prev1和prev2
    //空间复杂度仅有O(1)
    for (int i = 3; i <= n; i++)
    {
        curr = prev1 + prev2;
        prev2 = prev1;
        prev1 = curr;
    }
    return curr;
}

钢条切割问题

给定一段长度为$n$的钢条和一个价格表$p_i$，其中$p_i(i=1,2,\cdots,n)$，求钢条切割方案，使得销售收益$r_n$最大。

length i	1	2	3	4	5	6	7	8	9	10
price pi	1	5	8	9	10	17	17	20	24	30

分析：长度为n的钢条共有$2^{n-1}$种切割方案，如果一个最优解将钢条切割为$k (1 \leq k \leq n)$段，那么$n=i_1 + i_2 + \cdots + i_k$，得到最大收益 $r_n = p_{i_1} + p_{i_2} + \cdots + p_{i_k}$ 。一般地，我们可以将钢条的最优切割方案描述为：

$$ r_n = max(p_n , r_1+r_{n-1}, r_2+r_{n-2}, \cdots, r_{n-1}+r_1) $$

可以看到上面的式子中存在重复的计算。
最优切割方案的递归式描述为：

$$ r_n = \displaystyle \max_{1 \leq i \leq n} (p_i +r_{n-1}) $$

几种典型的解决方案如下：

cpp


// 简单的递归实现
int cutRod_recursive(vector<int> &price, int n)
{
    if (n == 0)
        return 0;
    int res = INT_MIN;
    for (int i = 1; i < n; i++)
    {
        int temp = price[i] + cutRod_recursive(price, n - i);
        res = max(res, temp);
    }
    return res;
}

// 带备忘录的自顶向下法
int cutRod_memo(vector<int> &price, int n)
{
    vector<int> memo(n + 1, 0); // 备忘录数组
    return cutRod_memo_helper(price, n, memo);
}
int cutRod_memo_helper(vector<int> &price, int n, vector<int> &memo)
{
    if (memo[n] > 0) // 已经计算过，直接返回
        return memo[n];
    if (n == 0) // 到达了叶子节点，返回0
        return 0;
    int res = INT_MIN; // 记录最大收益
    for (int i = 1; i < n; i++)
    {
        // 计算子问题的最大收益
        int temp = price[i] + cutRod_memo_helper(price, n - i, memo);
        res = max(res, temp); // 更新最大收益
    }
    memo[n] = res;
    return res;
}

// 自底向上法
int cutRod_bottomUp(vector<int> &price, int n)
{
    vector<int> dp(n + 1, 0); // 动态规划数组
    for (int i = 1; i <= n; i++)
    {
        int res = INT_MIN; // 记录最大收益
        for (int j = 1; j <= i; j++)
        {
            res = max(res, price[j] + dp[i - j]); // 计算子问题的最大收益
        }
        dp[i] = res; // 更新dp数组
    }
    return dp[n]; // 到达叶子节点，返回最大收益
}

动态规划原理

适合动态规划方法求解的问题有两个特征：最优子结构和子问题重叠。
使用动态规划的第一步：刻画最优解的结构。如果一个问题的最优解包含其子问题的最优解，则称该问题具有最优子结构。
适合用动态规划方法求解的最优化问题应该具备的第二个性质是子问题空间必须足够“小”，即问题的递归算法会反复地求解相同的子问题，而不是一直生成新的子问题。如果递归算法反复求解相同的子问题，我们就称最优化问题具有重叠子问题(overlapping subproblems) 性质。
动态规划算法通常这样利用重叠子问题性质：对每个子问题求解一次，将解存入一个表中，当再次需要这个子问题时直接查表，每次查表的代价为常量时间，进而动态规划算法将运行时间从递归算法的指数阶降为平方阶。

背包问题

0-1背包问题

给定$n$个物品，第$i$个物品的重量为$w_{i-1}$，价值为$v_{i-1}$，背包最大容量为$W$，求解将哪些物品装入背包，可使价值总和最大。
分析：对每个物品都有放入或不放入两种选择。

cpp


#include <iostream>
#include <vector>
using namespace std;

/**
 * @brief 0-1背包问题
 * @param W 背包容量
 * @param wt 物品的重量
 * @param val 物品的价值
 * @return 最大价值
 */
int knapsack_DP(int W, vector<int> &wt, vector<int> &val) 
{
    int n = wt.size(); // 物品个数
    vector<vector<int>> dp(n+1, vector<int>(W+1, 0)); // dp[i][j]表示前i件物品恰好放入一个容量为j的背包可以获得的最大价值
    for (int i = 1; i <= n; i++)
    {
        // 物品i的重量大于背包容量j，则不放入背包
        for (int j = 1; j <= W; j++)
        {
            if (wt[i-1] > j) // 物品i的重量大于背包容量j，则不放入背包
                dp[i][j] = dp[i-1][j];
            else // 物品i的重量小于等于背包容量j，则考虑两种选择：放入或不放入
                dp[i][j] = max(dp[i-1][j], val[i-1] + dp[i-1][j-wt[i-1]]); // 选择放入或不放入
                // 自底向上
        }
    }
    return dp[n][W];
}

完全背包问题

给定$n$种物品，第$i$种物品的重量为$w_{i-1}$，价值为$v_{i-1}$，背包最大容量为$W$，物品可以重复选取，求解将哪些物品装入背包，可使价值总和最大。
分析：物品i放入背包后仍然可以从前i个物品中选择。

cpp


/**
 * @brief 完全背包问题
 * @param W 背包容量
 * @param wt 物品的重量
 * @param val 物品的价值
 * @return 最大价值
 */
int unbounded_knapsack_DP(int W, vector<int> &wt, vector<int> &val) 
{
    int n = wt.size(); // 物品个数
    vector<vector<int>> dp(n+1, vector<int>(W+1, 0)); // dp[i][j]表示前i件物品恰好放入一个容量为j的背包可以获得的最大价值
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= W; j++)
        {
            if (wt[i-1] > j) // 物品i的重量大于背包容量j，则不放入背包
                dp[i][j] = dp[i-1][j];
            else // 物品i的重量小于等于背包容量j，则考虑两种选择：放入或不放入
                dp[i][j] = max(dp[i-1][j], val[i-1] + dp[i][j-wt[i-1]]); // 选择放入或不放入
        }
    }
    return dp[n][W];
}

零钱兑换问题

给定$n$种不同面值的硬币，每种硬币的数量无限，再给定一个总金额$M$，问最少需要多少个硬币凑出这个金额。

CPP


#include <iostream>
#include <vector>
#include <climits>
using namespace std;
/**
 * @brief 零钱兑换问题
 * @param coins 硬币面值
 * @param amount 总金额
 * @return 最少需要的硬币数
 */
int coin_change_DP(vector<int> &coins, int amount) {
    int n = coins.size(); // 硬币类别数
    vector<vector<int>> dp(n + 1, vector<int>(amount + 1, INT_MAX)); // 初始化dp数组为最大值

    // 初始化边界条件，当总金额为0时，所需硬币数为0
    for (int i = 0; i <= n; ++i) {
        dp[i][0] = 0;
    }

    // 动态规划递推过程
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= amount; ++j) {
            if (coins[i - 1] > j) {
                // 当前硬币面值大于目标金额，只能不选当前硬币
                dp[i][j] = dp[i - 1][j];
            } else {
                // 否则选择当前硬币或者不选当前硬币中所需硬币数较少的情况
                if (dp[i][j - coins[i - 1]] != INT_MAX) {
                    dp[i][j] = min(dp[i - 1][j], dp[i][j - coins[i - 1]] + 1);
                } else {
                    dp[i][j] = dp[i - 1][j]; // 无法用当前硬币凑出 j
                }
            }
        }
    }

    // 如果最终结果仍为初始最大值，说明无法凑出目标金额
    return dp[n][amount] == INT_MAX ? -1 : dp[n][amount];
}

/**
 * @brief 零钱兑换问题优化
 * @param coins 硬币面值
 * @param amount 总金额
 * @return 最少需要的硬币数
 */
int coin_change_DP_v2(vector<int> &coins, int amount) 
{
    int n = coins.size(); // 硬币类别数，即有多少种不同面值的硬币

    // dp[j] 表示凑够总金额 j 所需的最少硬币数，初始化为 INT_MAX 表示目前还未找到有效的凑法
    vector<int> dp(amount + 1, INT_MAX); 
    dp[0] = 0; // 凑够总金额 0 需要 0 个硬币，这是基础情况，作为后续计算的起点

    // 遍历每一种硬币面值
    for (int coin : coins) {
        // 从当前硬币面值coin开始，到目标总金额amount，依次尝试更新dp数组
        for (int j = coin; j <= amount; ++j) {
            // 只有当金额 j - coin 可以被凑出（dp[j - coin] 不是初始的INT_MAX）时，
            // 才考虑使用当前硬币 coin 来更新凑出金额 j 所需的最少硬币数
            if (dp[j - coin]!= INT_MAX) {
                // 选择当前dp[j]（之前可能的凑法得到的最少硬币数）和使用当前硬币凑出金额 j 的情况（dp[j - coin] + 1）中硬币数更少的那个来更新dp[j]
                dp[j] = min(dp[j], dp[j - coin] + 1);
            }
        }
    }

    // 如果最终凑出目标金额amount对应的dp[amount]仍为INT_MAX，说明无法凑出该金额，返回 -1；否则返回凑出该金额所需的最少硬币数
    return dp[amount] == INT_MAX? -1 : dp[amount];
}


int main() {
    vector<int> coins;
    int amount;

    // 测试用例 1
    coins = {1, 2, 5};
    amount = 11;
    cout << "Test 1: " << coin_change_DP(coins, amount) << endl; // 输出 3 (5+5+1)

    // 测试用例 2
    coins = {2};
    amount = 3;
    cout << "Test 2: " << coin_change_DP(coins, amount) << endl; // 输出 -1

    // 测试用例 3
    coins = {186, 419, 83, 408};
    amount = 6249;
    cout << "Test 3: " << coin_change_DP(coins, amount) << endl; // 输出 20

    // 测试用例 4
    coins = {1};
    amount = 0;
    cout << "Test 4: " << coin_change_DP(coins, amount) << endl; // 输出 0

    return 0;
}

零钱兑换问题2

给定$n$种不同面值的硬币，每种硬币可以重复选取，目标金额为$M$，求凑出目标金额的硬币组合数量。
分析：定义 dp[j] 为目标金额 $j$ 的硬币组合数。
dp[0] = 1：凑出金额 0 的唯一组合是“不选任何硬币”。
对于每个硬币 coins[i]，更新所有可能的金额 $j$ ：

$$ dp[j] = dp[j] + dp[j - coins[i]] $$

意思是：不使用当前硬币的组合数（原本的 dp[j]）加上使用当前硬币的组合数（dp[j - coins[i]]）。
对比前面的斐波那契数列，这个问题有点退化到斐波那契数列问题了。

cpp


/**
 * @brief 计算凑出目标金额的硬币组合数量
 * @param coins 硬币面值数组
 * @param M 目标金额
 * @return 符合条件的组合数量
 */
int count_combinations(vector<int>& coins, int M) {
    vector<int> dp(M + 1, 0); // dp[j] 表示凑出金额 j 的组合数量
    dp[0] = 1; // 初始化：凑出金额 0 的组合数为 1

    // 遍历每种硬币
    for (int coin : coins) {
        for (int j = coin; j <= M; ++j) {
            dp[j] += dp[j - coin];
        }
    }

    return dp[M];
}

最长公共子序列（Longest Common Subsequence）

公共子序列是指在两个字符串中都以相同顺序出现的字符序列，但不要求是连续的。最长公共子序列问题（Longest-Common-Subsequence Problem，简称 LCS 问题）：给定两个序列（通常是字符串或者数组等形式） $ A$ 和 $B$ ，找到它们的最长公共子序列（LCS）。
例如输入：$ A = \text{"abcde"}, B = \text{"ace"}$，输出：LCS 是 "ace"，长度为 3。

该问题广泛应用于基因序列分析、文本比较和差异计算（如 diff 工具）、数据传输中的相似度检测等。

动态规划是解决 LCS 问题的经典方法。

状态定义 定义一个二维数组 dp[i][j]：表示字符串 $A[0 \ldots i-1] $和 $B[0 \ldots j-1]$ 的最长公共子序列长度。
状态转移方程 如果 $A[i-1] == B[j-1] $，有 $dp[i][j] = dp[i-1][j-1] + 1 $当前字符匹配，LCS 长度增加 1。否则$ dp[i][j] = \max(dp[i-1][j], dp[i][j-1])$ 当前字符不匹配，取上一个子问题的最优解。
初始化 dp[0][j] = 0：当 $A$ 是空串时，LCS 长度为 0。dp[i][0] = 0：当 $B$ 是空串时，LCS 长度为 0。
最终 dp[m][n] 就是 $A$ 和 $B$ 的 LCS 长度，其中 $m$ 是 $A$ 的长度，$n$ 是 $B$ 的长度。

cpp


#include <iostream>
#include <vector>
#include <string>
using namespace std;

/**
 * @brief 计算两个字符串的最长公共子序列长度
 * @param A 第一个字符串
 * @param B 第二个字符串
 * @return 最长公共子序列的长度
 */
int longest_common_subsequence(const string& A, const string& B) {
    int m = A.size(), n = B.size();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0)); // 初始化 dp 数组

    // 动态规划填表
    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (A[i - 1] == B[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1; // 当前字符匹配
            } else {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]); // 不匹配，取较大值
            }
        }
    }

    return dp[m][n]; // 返回 LCS 的长度
}

/**
 * @brief 构造最长公共子序列
 */
string construct_lcs(const string& A, const string& B, const vector<vector<int>>& dp) {
    string lcs = "";
    int i = A.size(), j = B.size();

    while (i > 0 && j > 0) {
        if (A[i - 1] == B[j - 1]) {
            lcs = A[i - 1] + lcs; // 匹配字符，加入 LCS
            --i; --j;
        } else if (dp[i - 1][j] > dp[i][j - 1]) {
            --i; // 向上移动
        } else {
            --j; // 向左移动
        }
    }

    return lcs;
}

int main() {
    string A = "abcde", B = "ace";
    int lcs_length = longest_common_subsequence(A, B);
    cout << "最长公共子序列长度为: " << lcs_length << endl;

    vector<vector<int>> dp(A.size() + 1, vector<int>(B.size() + 1, 0));
    for (int i = 1; i <= A.size(); ++i) {
        for (int j = 1; j <= B.size(); ++j) {
            if (A[i - 1] == B[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    cout << "最长公共子序列为: " << construct_lcs(A, B, dp) << endl;
    return 0;
}

时间复杂度 $O(m \cdot n)$，其中 $m$ 是字符串 $A$ 的长度，$n$ 是字符串 $B$ 的长度。如果只需要 LCS 长度，可以使用一维数组优化，空间复杂度为 $O(\min(m, n))$。如果需要构造 LCS，则需要 $O(m \cdot n)$ 的二维数组。