C++动态规划的解释、案例和完整代码（斐波那契数列和背包问题）+需要用到动态规划算法的常见案例

动态规划的解释

动态规划（Dynamic Programming，简称 DP）是一种用于解决优化问题的算法策略，它通过将一个复杂的问题分解为一系列相互关联的子问题，并避免重复计算子问题的解，从而高效地求解原问题。

其核心思想包含以下几点：

1. 分解问题：把原问题拆分成多个子问题，这些子问题通常具有相似的结构，而且子问题的解能够帮助构建原问题的解。例如，计算斐波那契数列时，第 n 个斐波那契数可以依赖于第 n - 1 个和第 n - 2 个斐波那契数，这就是把计算整个数列的大问题分解成计算一个个具体位置数字的子问题。
2. 记忆化（避免重复计算）：在求解子问题的过程中，会记录已经求得的子问题的解（通常使用数组等数据结构来存储），当下一次再遇到同样的子问题时，就可以直接使用之前记录的结果，而不用重新计算，大大提高了效率。比如在计算有重叠子问题的递归函数时，通过记录中间结果，能减少很多不必要的重复递归调用。
3. 最优子结构：原问题的最优解可以由子问题的最优解组合而成。例如，在背包问题中，如果想找到能装入背包获得最大价值的物品组合这个最优解，那么对于背包容量更小、物品数量更少等子情况的最优解可以被用来构建整体的最优解。

C++ 案例之斐波那契数列

1. 问题描述

斐波那契数列指的是这样一个数列：0、1、1、2、3、5、8、13、21、34、…… ，从第三项开始，每一项都等于前两项之和，现在要求用动态规划的方法计算斐波那契数列的第 n 项。

2. 代码实现

cpp

#include <iostream>
#include <vector>

using namespace std;

// 使用动态规划计算斐波那契数列第n项
int fibonacci(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;

    // 创建一个vector来存储已经计算过的斐波那契数，初始化为0
    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]
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    return dp[n];
}

int main() {
    int n = 10;  // 这里可以修改n的值来计算不同位置的斐波那契数
    cout << "斐波那契数列第 " << n << " 项的值为: " << fibonacci(n) << endl;
    return 0;
}

在上述代码中：

• 首先处理了 n 为 0 和 1 这两种基础情况，直接返回对应的值。
• 然后创建了 vector<int> 类型的 dp 数组，用于存储已经计算过的斐波那契数，通过循环按照斐波那契数列的定义（即状态转移方程 dp[i] = dp[i - 1] + dp[i - 2]）依次计算并存储每一项的值，最后返回 dp[n] 就是所求的第 n 项斐波那契数。

C++ 案例之背包问题

1. 问题描述

有一个背包，它的容量为 W 千克，有 n 个物品，每个物品都有重量 weight[i] 和价值 value[i]，现在要在有限的背包容量下选择物品装入背包，使得背包内物品的总价值最大。

2. 代码实现

cpp

#include <iostream>
#include <vector>

using namespace std;

// 计算能装入背包的最大价值
int knapsack(int W, vector<int> weight, vector<int> value, int n) {
    // 创建二维动态规划数组，dp[i][w] 表示前i个物品在背包容量为w时能获得的最大价值
    vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));

    for (int i = 1; i <= n; ++i) {
        for (int w = 1; w <= W; ++w) {
            if (weight[i - 1] <= w) {
                // 状态转移方程，选择放入或不放入当前物品中价值较大的情况
                dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weight[i - 1]] + value[i - 1]);
            } else {
                dp[i][w] = dp[i - 1][w];
            }
        }
    }
    cout<<endl;
    for(int i = 0;i<=n;i++){
		for(int j = 0;j<=W;j++){
			cout<<dp[i][j]<<" ";
		}
		cout<<endl;
	}
	
    return dp[n][W];
}

int main() {
    int W = 5;  // 背包容量
    vector<int> weight = {2, 1, 3, 4, 5};  // 物品重量
    vector<int> value = {3, 2, 4, 7, 10};  // 物品价值
    int n = weight.size();

    cout << "背包能装入的最大价值为: " << knapsack(W, weight, value, n) << endl;

    return 0;
}

在这个背包问题的代码中：

• 首先创建了二维的 dp 数组 vector<vector<int>> dp，其中 dp[i][w] 表示前 i 个物品在背包容量为 w 时能获得的最大价值。
• 通过两层嵌套循环遍历物品数量和背包容量，根据当前物品的重量与背包剩余容量的关系来确定状态转移方程。如果当前物品重量小于等于背包容量，就选择放入该物品或者不放入该物品中能获得更大价值的情况（即 max(dp[i - 1][w], dp[i - 1][w - weight[i - 1]] + value[i - 1])）；如果当前物品重量大于背包容量，那就只能不放入该物品，价值就和之前的情况一样（即 dp[i - 1][w]）。
• 最后返回 dp[n][W] 就是背包能装入的最大价值。

这些只是动态规划在 C++ 中的简单示例应用，动态规划还广泛应用于许多其他复杂的优化问题中，比如最长公共子序列问题、编辑距离问题等，它们的核心思路都是通过上述提到的分解问题、记忆化以及利用最优子结构来实现高效求解。

分析

以上代码输出如下

背包能装入的最大价值为:10
0 0 0 0 0 0
0 0 3 3 3 3
0 2 3 5 5 5
0 2 3 5 6 7
0 2 3 5 7 9
0 2 3 5 7 10

通过对比我们可以发现，动态规划的方程满足高中里面的排列组规律，会结合相应的物品大小，去相互组合，比如重3斤的物品和重1斤的物品组合，重3斤的物品和重2斤的物品组合，这个公式

// 状态转移方程，选择放入或不放入当前物品中价值较大的情况
dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weight[i - 1]] + value[i - 1]);

刚好可以满足这样的规律进行比较，这和高中数学里面的排列组合符合，又和构造函数很相似，是通过题目规律构造一个符合题解的公式，只不过使用代码进行赋值比较。原理上极为相似。

以下是一些需要用到动态规划算法的常见案例：