理论讲解
动态规划（Dynamic Programming）是一种解决问题的算法设计方法，它将问题分解为更小的子问题，并通过保存子问题的解来构建大问题的解。动态规划常用于优化递归算法，避免重复计算，并通常适用于具有重叠子问题和最优子结构性质的问题。
动态规划的核心思想是从底向上解决问题，通过先解决子问题，再根据子问题的解构建更大规模的问题的解。一般来说，动态规划可以分为以下几个步骤：
- 定义状态：确定原问题和子问题中需要求解的状态变量，并描述其含义。
- 定义状态转移方程：根据子问题之间的关系，利用递推公式或者递归方程表达问题的解与子问题的关系。
- 初始化：确定初始状态的值，即最简单的子问题的解。
- 递推求解：按照定义的状态转移方程，从初始状态开始逐步向上求解更复杂的问题，直到解决原问题。
- 求解结果：根据最终定义的状态，得到原问题的解。
动态规划的实现可以采用迭代（自底向上）或递归（自顶向下）的方式。迭代法从最小的子问题开始解决，逐步推导出更大规模的问题的解。递归法则从原问题开始，根据子问题的关系递归求解子问题，直到达到基本情况。
动态规划在解决许多优化问题时非常有效，如最短路径问题、背包问题、字符串编辑距离问题等。它通过将复杂问题分解为简单问题，并合理利用子问题的解，避免了重复计算，提高了计算效率。
举个例子
01背包问题是动态规划中比较经典的问题之一，它的题目描述为：给定一个固定大小、能够携带重量为W的背包，以及一组物品，每个物品有自己的重量和价值，在保证不超过背包容量的前提下，如何选择物品放入背包，使得背包中物品的总价值最大。
动态规划可以非常好地解决这个问题。我们用一个二维数组 dp[i][j] 来表示携带重量不超过 j 的前 i 个物品中，所能获得的最大价值，其中 i 表示物品的数量，j 表示背包的重量。则状态转移方程为：
dp[i][j] = max(dp[i-1][j], dp[i-1][j-wi] + vi)，其中 wi 表示第 i 个物品的重量，vi 表示第 i 个物品的价值初始状态为 dp[0][j]=0，dp[i][0]=0。其中 dp[0][j] 表示没有物品可选时，任何背包都是无法装满的，因此价值为 0；dp[i][0] 表示背包重量为 0，则无论有多少物品，其价值也都是 0。
通过以上状态转移方程，我们可以通过填写 dp 数组来求解出携带重量不超过 W 的最大价值，即 dp[n][W]。
下面用一个具体的例子来说明如何使用动态规划求解01背包问题：
假设有5个物品，其重量和价值分别为：
w = [2, 2, 6, 5, 4]
v = [6, 3, 5, 4, 6]而且固定大小为10的背包。那么我们可以初始化 dp 数组为：
dp[0][j]=0
dp[i][0]=0然后我们根据状态转移方程填写 dp 数组：
dp[i][j] = max(dp[i-1][j], dp[i-1][j-wi] + vi)
当 i=1, j=1 时： dp[1][1] = max(dp[0][1], dp[0][-1] + 6) = max(0, 6) = 6
当 i=1, j=2 时： dp[1][2] = max(dp[0][2], dp[0][0] + 3) = max(0, 3) = 3
当 i=1, j=3 时： dp[1][3] = max(dp[0][3], dp[0][1] + 5) = max(0, 5) = 5
当 i=1, j=4 时： dp[1][4] = max(dp[0][4], dp[0][2] + 4) = max(0, 4) = 4
当 i=1, j=5 时： dp[1][5] = max(dp[0][5], dp[0][3] + 6) = max(0, 6) = 6
当 i=1, j=6 时： dp[1][6] = max(dp[0][6], dp[0][4] + 0) = max(0, 0) = 0
当 i=1, j=7 时： dp[1][7] = max(dp[0][7], dp[0][5] + 0) = max(0, 0) = 0
当 i=1, j=8 时： dp[1][8] = max(dp[0][8], dp[0][6] + 0) = max(0, 0) = 0
当 i=1, j=9 时： dp[1][9] = max(dp[0][9], dp[0][7] + 0) = max(0, 0) = 0
当 i=1, j=10 时： dp[1][10] = max(dp[0][10], dp[0][8] + 0) = max(0, 0) = 0
当 i=2, j=1 时： dp[2][1] = max(dp[1][1], dp[1][-1] + 0) = max(6, 0) = 6
当 i=2, j=2 时： dp[2][2] = max(dp[1][2], dp[1][0] + 0) = max(3, 0) = 3
当 i=2, j=3 时： dp[2][3] = max(dp[1][3], dp[1][1] + 0) = max(5, 0) = 5
当 i=2, j=4 时： dp[2][4] = max(dp[1][4], dp[1][2] + 0) = max(4, 0) = 4
当 i=2, j=5 时： dp[2][5] = max(dp[1][5], dp[1][3] + 6) = max(6, 6) = 6
当 i=2, j=6 时： dp[2][6] = max(dp[1][6], dp[1][4] + 0) = max(0, 0) = 0
当 i=2, j=7 时： dp[2][7] = max(dp[1][7], dp[1][5] + 3) = max(0, 3) = 3
当 i=2, j=8 时： dp[2][8] = max(dp[1][8], dp[1][6] + 0) = max(0, 0) = 0
当 i=2, j=9 时： dp[2][9] = max(dp[1][9], dp[1][7] + 5) = max(0, 5) = 5
当 i=2, j=10 时： dp[2][10] = max(dp[1][10], dp[1][8] + 4) = max(0, 4) = 4
当 i=3, j=1 时： dp[3][1] = max(dp[2][1], dp[2][-5] + 0) = max(6, 0) = 6
......最终我们得到的 dp 数组为：
0 1 2 3 4 5 6 7 8 9 10
0 0 0 0 0 0 0 0 0 0 0 0
1 0 6 3 5 4 6 0 0 0 0 0
2 0 6 3 5 4 6 0 3 0 5 4
3 0 6 3 5 11 9 5 8 5 10 9
4 0 6 3 5 11 12 5 9 6 10 15
5 0 6 3 5 11 12 5 9 12 14 15那么我们可以选择放入物品1、2、4和5，可以得到最大价值为 19。
通过以上例子，我们可以看到动态规划方便地解决了01背包问题，同时也能够在处理复杂问题时取得更高的效率。
完整代码
#include <iostream>
#include <vector>
using namespace std;
int knapsack(int W, vector<int>& wt, vector<int>& val) {
int n = wt.size();
vector<vector<int>> dp(n+1, vector<int>(W+1, 0)); // 初始化dp数组
for (int i = 1; i <= n; i++) { // 遍历物品
for (int j = 1; j <= W; j++) { // 遍历背包容量
if (wt[i-1] > j) { // 当前物品重量大于背包容量
dp[i][j] = dp[i-1][j]; // 直接继承前 i-1 个物品的最大价值
}
else {
dp[i][j] = max(dp[i-1][j], dp[i-1][j-wt[i-1]] + val[i-1]); // 比较选择当前物品和不选当前物品的最大价值
}
}
}
return dp[n][W]; // 返回携带重量不超过W的前n个物品的最大价值
}
int main() {
int W = 10;
vector<int> wt = {2, 2, 6, 5, 4};
vector<int> val = {6, 3, 5, 4, 6};
int maxVal = knapsack(W, wt, val);
cout << "The maximum value is: " << maxVal << endl;
return 0;
}