动态规划详解及 C/C++ 示例

动态规划是一种常用的算法设计技术，用于解决具有重叠子问题和最优子结构特性的问题。它通过将问题分解为较小的子问题，并存储子问题的解以避免重复计算，从而高效地解决问题。

一、基本概念

1. 多阶段决策问题

这类问题需要经过多个阶段的决策来达到目标，每个阶段的决策会影响后续阶段的状态和决策选择。例如，背包问题中，选择放或不放某个物品就是一个阶段的决策，这个决策会影响背包的剩余容量，进而影响后续物品的放置决策。

2. 最优子结构

一个问题的最优解包含其子问题的最优解。例如，斐波那契数列的第 n 项等于第 n - 1 项和第 n - 2 项之和，这里的第 n 项的最优解（即正确的值）就包含了第 n - 1 项和第 n - 2 项的最优解。

3. 重叠子问题

在递归求解过程中，许多子问题会被重复计算。例如，递归计算斐波那契数列时，多个分支都会计算相同的斐波那契数，动态规划通过保存已解决子问题的解来避免重复计算。

二、动态规划算法的步骤

1. 确定状态

状态定义是动态规划的关键。状态通常表示问题中的某个中间结果或当前所处的情况。例如，在斐波那契数列问题中，状态可以定义为第 n 个斐波那契数的值，在背包问题中，状态可以定义为前 i 个物品放入容量为 j 的背包中所能获得的最大价值。

2. 确定状态转移方程

状态转移方程描述了不同状态之间的关系，即如何从前一个或多个状态转移到当前状态。例如，斐波那契数列的状态转移方程为 f(n) = f(n - 1) + f(n - 2)，背包问题的状态转移方程为 dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])，其中 weight[i] 和 value[i] 分别是第 i 个物品的重量和价值，dp[i][j] 表示前 i 个物品放入容量为 j 的背包中的最大价值。

3. 确定初始条件和边界条件

初始条件是问题的起始状态，边界条件是状态的范围限制。例如，斐波那契数列的初始条件为 f(0) = 0、f(1) = 1，边界条件为 n 为非负整数；背包问题的初始条件可以是 dp[0][j] = 0（没有物品放入背包时价值为 0），边界条件可以是 j 不能超过背包的最大容量。

4. 计算最优解的值

按照状态转移方程递推地计算各个状态的最优值，通常使用自底向上的方式进行计算，即从初始状态开始逐步计算到最终状态。

5. 构造最优解

如果需要构造具体的最优解路径，可在计算最优值的同时记录相关决策信息，然后通过回溯这些决策信息来构造最优解。

三、斐波那契数列示例代码（C/C++）

#include <iostream>
using namespace std;

int fibonacci(int n) {
    if (n < 0) {
        return -1; // 错误处理
    }
    int dp[n + 1];
    dp[0] = 0;
    if (n >= 1) {
        dp[1] = 1;
    }
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

int main() {
    int n = 10;
    cout << "fibonacci(" << n << ") = " << fibonacci(n) << endl;
    return 0;
}

四、背包问题示例代码（C/C++）

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

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

int main() {
    vector<int> values = {60, 100, 120};
    vector<int> weights = {10, 20, 30};
    int capacity = 50;
    cout << "knapsack: max value = " << knapsack(values, weights, capacity) << endl;
    return 0;
}

五、代码解释

1. 斐波那契数列代码解释

首先创建一个大小为 n + 1 的数组 dp 来存储斐波那契数列的值。将 dp[0] 初始化为 0，当 n 大于等于 1 时，将 dp[1] 初始化为 1。然后从第 2 项开始，利用状态转移方程 dp[i] = dp[i - 1] + dp[i - 2] 依次计算每个斐波那契数的值，最终返回第 n 项的值。

2. 背包问题代码解释

创建一个二维数组 dp，其中 dp[i][j] 表示前 i 个物品放入容量为 j 的背包中的最大价值。遍历每个物品（从 1 到 n）和每个可能的背包容量（从 1 到 capacity）。对于每个物品，如果其重量大于背包容量 j，则无法放入背包，此时 dp[i][j] 的值与 dp[i - 1][j] 相同。否则，比较放入该物品后的价值（dp[i - 1][j - weights[i - 1]] + values[i - 1]）和不放入该物品时的价值（dp[i - 1][j]），将较大的值赋给 dp[i][j]。最终返回 dp[n][capacity]，即为背包的最大价值。