一、什么是动态规划？

动态规划（Dynamic Programming, DP）是一种解决多阶段决策问题的算法思想。它通过把原问题分解为重叠的子问题，并保存子问题的解，避免大量重复计算，从而将指数级的时间复杂度降为多项式级别。
适用场景：

问题可以分解成相互依赖的子问题
子问题会被多次重复计算
子问题的最优解能构成原问题的最优解（最优子结构）

二、核心概念

状态定义

用一个或多个变量描述当前所处的情形，通常用数组下标表示。
例如 dp[i] 表示“前 i 个物品的最大价值”，或 dp[i][j] 表示“字符串 A 的前 i 个字符与字符串 B 的前 j 个字符的最长公共子序列长度”。
状态转移方程

描述状态之间如何推导的数学表达式，是 DP 的核心。
比如 0-1 背包：dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])
初始条件 / 边界

最小的子问题的解，通常是 dp[0]、dp[0][0] 等。
计算顺序

确定按什么顺序填充 DP 表格，保证计算当前状态时，依赖的状态已经算过。

三、动态规划的一般解题步骤

分析问题是否有重叠子问题和最优子结构
定义状态：明确 dp[i] 或 dp[i][j] 代表什么
推导状态转移方程
初始化边界
确定遍历顺序，用代码实现
可能的空间优化（用滚动数组代替二维数组）

四、经典例题（C++ 代码）

斐波那契数列
问题：求第 n 项斐波那契数 F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2)

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

long long fib(int n) {
    if (n <= 1) return n;
    vector<long long> dp(n + 1);
    dp[0] = 0;
    dp[1] = 1;
    for (int i = 2; i <= n; ++i) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

int main() {
    cout << fib(50) << endl; 
    return 0;
}

背包问题
问题：有 n 个物品，每个物品重量 w[i]，价值 v[i]，背包容量为 W，每种物品只能选 0 或 1 个，求最大总价值。

状态定义：dp[i][j] —— 前 i 个物品放入容量为 j 的背包的最大价值。

int knapsack(int W, vector<int> weight, vector<int> value) {
    int n = weight.size();
    vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));

    for (int i = 1; i <= n; ++i) {
        int w = weight[i - 1], v = value[i - 1];
        for (int j = 1; j <= W; ++j) {
            if (j < w)
                dp[i][j] = dp[i - 1][j];
            else
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w] + v);
        }
    }
    return dp[n][W];
}

五、总结

动态规划是一门需要大量练习才能熟练掌握的技艺。本质是 “以空间换时间”，通过数组（表格）记录子问题的解，避免重复运算。学习路线建议：

先用递归写暴力解，画出递归树，发现重叠子问题
改为记忆化搜索（自顶向下）
推导 DP 表（自底向上）