算法心传·DP – 将去未还的随笔

动态规划，江湖人称“DP”，是算法面试中的“拦路虎”，也是竞赛选手的“看家本领”。很多人觉得DP难，是因为它不像排序、搜索那样有固定的模板，更像是一种“算法思想”——你需要对问题进行抽象、定义状态、寻找转移。

本文将带你从零开始，系统梳理动态规划的核心思想，通过大量经典案例，帮你建立DP的解题思维框架。

一、什么是动态规划

1. 一个朴素的理解

动态规划的核心思想是：将一个复杂的问题分解成若干个简单的子问题，并且保存子问题的解，避免重复计算，从而高效地得到原问题的解。
它通常用于求解最优化问题（最大值、最小值、方案数等），这些问题的共同特征是：

具有重叠子问题：子问题在求解过程中会被反复用到。
具有最优子结构：原问题的最优解包含子问题的最优解。

2. 动态规划与分治和贪心

算法	核心特点	典型代表
分治	子问题相互独立，无重叠	归并排序
贪心	每一步取局部最优，不可回退	最小生成树、Dijkstra
动态规划	子问题重叠，记录状态，全局最优	背包、LCS、最短路径

DP本质上是“带备忘录的暴力搜索”——它枚举了所有可能的状态，但通过状态转移避免重复计算。

二、动态规划的核心要素

任何一个DP问题，都可以用以下四个步骤来拆解：

定义状态（State）
用数组dp[i]或dp[i][j]表示某个阶段的最优解或方案数。状态定义是DP的灵魂，定义得巧，问题就解决了一半。
确定状态转移方程（Transition）
描述当前状态如何由之前的状态推导出来。这是DP的“递推公式”。
初始化（Initialization）
确定边界状态的值，通常是递推的起点。
确定遍历顺序（Order）
根据依赖关系，决定循环的方向（正序、倒序、按层等）。

三、一维DP

1.斐波那契数列

B2064 斐波那契数列 – 洛谷
问题：求第n个斐波那契数，F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2)。
这是最直观的DP模型。
状态定义：dp[i]表示第i个斐波那契数。
转移方程：dp[i] = dp[i-1] + dp[i-2]
初始化：dp[0] = 0, dp[1] = 1

这一段比较简单，直接给出代码供读者参考：

long long fib(int n) {
    if (n < 2) return n;
    long long a = 0, b = 1;
    for (int i = 2; i <= n; ++i) {
        int c = a + b;
        a = b;
        b = c;
    }
    return b;
}

关键思想：DP的本质就是用空间换时间，这里用两个变量就实现了状态滚动，复杂度O(n)。

2.爬楼梯问题

P1255 数楼梯 – 洛谷
问题：每次可以爬1级或2级台阶，求爬到第n级有多少种不同方法。
这是斐波那契的“应用题”。
状态定义：dp[i]表示到达第i级台阶的方法数。
转移方程：dp[i] = dp[i-1] + dp[i-2]（因为最后一步要么从i-1跨1步，要么从i-2跨2步）
初始化：dp[1] = 1, dp[2] = 2

代码如下：

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

总结：一维DP通常状态简单，递推直观，适合作为DP的启蒙。

四、二维DP和路径问题

1. 不同路径（机器人走格子）

问题：m×n网格，机器人从左上角走到右下角，每次只能向下或向右，求不同路径数。
状态定义：dp[i][j]表示从起点走到(i,j)的路径数。
转移方程：dp[i][j] = dp[i-1][j] + dp[i][j-1]（只能从上边或左边来）
初始化：第一行和第一列均为1（只有一条路径）

代码：

int uniquePaths(int m, int n) {
    vector<vector<int>> dp(m, vector<int>(n, 1));
    for (int i = 1; i < m; ++i) {
        for (int j = 1; j < n; ++j) {
            dp[i][j] = dp[i-1][j] + dp[i][j-1];
        }
    }
    return dp[m-1][n-1];
}

空间优化：可以用一维数组滚动，因为dp[i][j]只依赖上一行和当前行左边。

2. 最小路径和

问题：给定带权值的网格，从左上角到右下角，路径和最小。
状态定义：dp[i][j]表示从起点到(i,j)的最小路径和。
转移方程：dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])
初始化：dp[0][0] = grid[0][0]，第一行和第一列累加。

代码如下：

int minPathSum(vector<vector<int>>& grid) {
    int m = grid.size(), n = grid[0].size();
    vector<vector<int>> dp(m, vector<int>(n));
    dp[0][0] = grid[0][0];
    for (int i = 1; i < m; ++i) dp[i][0] = dp[i-1][0] + grid[i][0];
    for (int j = 1; j < n; ++j) dp[0][j] = dp[0][j-1] + grid[0][j];
    for (int i = 1; i < m; ++i) {
        for (int j = 1; j < n; ++j) {
            dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]);
        }
    }
    return dp[m-1][n-1];
}

总结：二维DP常见于网格、矩阵类问题，关键在于理清依赖方向。

五、背包问题

背包问题是DP中非常经典的一类，也是面试高频。我们重点介绍01背包和完全背包。

1. 01背包

问题：有N件物品，每件重量w[i]，价值v[i]，背包容量W，每件物品最多选一次，求能装的最大价值。
转移方程：

二维：dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])
一维：dp[j] = max(dp[j], dp[j - w[i]] + v[i])，注意j必须倒序遍历，确保每个物品只取一次。

代码：

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

2. 完全背包

问题：每件物品可以选无限次。
区别：只需将内层循环改为正序，因为可以重复使用同一物品。

代码：

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

总结：背包问题的核心在于“选与不选”的决策，以及遍历顺序对物品使用次数的控制。

六、区间DP

区间DP是在区间上进行动态规划，通常用于求解一个区间内的最优值（如合并石子、回文分割等）。

1. 石子合并（经典区间DP）

问题：N堆石子排成一条线，每次合并相邻两堆，代价为两堆石子数之和，求合并成一堆的最小总代价。
状态定义：dp[i][j]表示合并第i堆到第j堆的最小代价。
转移方程：dp[i][j] = min(dp[i][k] + dp[k+1][j] + sum(i,j))，其中i ≤ k < j。
枚举顺序：按区间长度从小到大枚举。

代码框架：

int stoneMerge(vector<int>& stones) {
    int n = stones.size();
    vector<int> prefix(n + 1, 0);
    for (int i = 1; i <= n; ++i) {
        prefix[i] = prefix[i-1] + stones[i-1];
    }
    
    vector<vector<int>> dp(n, vector<int>(n, 0));
    // 区间长度从2到n
    for (int len = 2; len <= n; ++len) {
        for (int i = 0; i + len <= n; ++i) {
            int j = i + len - 1;
            dp[i][j] = INT_MAX;
            for (int k = i; k < j; ++k) {
                int cost = dp[i][k] + dp[k+1][j] + prefix[j+1] - prefix[i];
                dp[i][j] = min(dp[i][j], cost);
            }
        }
    }
    return dp[0][n-1];
}

总结：区间DP的特征是状态由小区间合并而来，循环顺序常按长度递增。

七、树形DP

树形DP是在树结构上做DP，通常用DFS后序遍历实现。

1. 7.1 树的最大独立集（打家劫舍III）

问题：二叉树，相邻节点不能同时选，求能选的最大权值和。
状态定义：每个节点返回两个值：[选当前节点，不选当前节点]的最大收益。
转移：

选当前节点：左右孩子都不能选 → val + left[1] + right[1]
不选当前节点：左右孩子可选可不选 → max(left[0], left[1]) + max(right[0], right[1])

代码：

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

pair<int, int> dfs(TreeNode* node) {
    if (!node) return {0, 0};
    auto left = dfs(node->left);
    auto right = dfs(node->right);
    int rob_cur = node->val + left.second + right.second;
    int not_rob = max(left.first, left.second) + max(right.first, right.second);
    return {rob_cur, not_rob};
}

int rob(TreeNode* root) {
    auto res = dfs(root);
    return max(res.first, res.second);
}

总结：树形DP的关键是后序收集子节点信息，再向上合并。

八、状态压缩DP

当状态维度很多（比如集合、排列）时，可以用二进制位表示状态，常见于NP难问题的小规模求解。

1. 旅行商问题（TSP）

问题：给定城市之间的距离，从0出发，经过所有城市一次，回到起点，求最短路径。
状态定义：dp[mask][i]表示已经访问过的城市集合为mask（二进制），当前在城市i的最短路径。
转移：dp[mask][i] = min(dp[mask ^ (1<<i)][j] + dist[j][i])

核心代码：

int tsp(vector<vector<int>>& dist) {
    int n = dist.size();
    int fullMask = (1 << n) - 1;
    const int INF = 1e9;
    vector<vector<int>> dp(1 << n, vector<int>(n, INF));
    dp[1][0] = 0;  // 从0出发，只访问了0
    for (int mask = 0; mask < (1 << n); ++mask) {
        for (int i = 0; i < n; ++i) {
            if (dp[mask][i] == INF) continue;
            for (int j = 0; j < n; ++j) {
                if (!(mask >> j & 1)) {  // j未访问
                    int newMask = mask | (1 << j);
                    dp[newMask][j] = min(dp[newMask][j], dp[mask][i] + dist[i][j]);
                }
            }
        }
    }
    int ans = INF;
    for (int i = 0; i < n; ++i) {
        ans = min(ans, dp[fullMask][i] + dist[i][0]);
    }
    return ans;
}

总结：状态压缩DP常用于“集合覆盖”“哈密顿路径”等组合优化问题，n通常≤20。

九、DP优化技巧

当DP的复杂度不满足要求时，可以尝试以下优化：

空间优化：滚动数组（如背包、路径问题）。
单调队列优化：用于滑动窗口类DP，如dp[i] = min(dp[j]) + cost，j在滑动区间内。
斜率优化：将转移方程转化为直线形式，维护凸包，用于dp[i] = min(dp[j] + (x[i]-x[j])^2)类问题。
四边形不等式优化：用于区间DP，当决策点具有单调性时，可将复杂度从O(n^3)降到O(n^2)。

十、总结与心法

10.1 如何识别DP问题？

问题求最值、方案数
存在“重叠子问题”
状态可由之前状态推导

10.2 DP解题四步法

定义状态：想清楚一维还是多维，每个状态代表什么。
写转移方程：思考“最后一步”或“当前决策”，用之前状态表示当前状态。
初始化：边界条件往往就是递推的起点。
确定顺序：按状态依赖关系决定循环方向。

10.3 常见DP模型

一维线性DP：斐波那契、爬楼梯、最大子序和
二维网格DP：路径数、最小路径和
背包DP：0-1背包、完全背包、多重背包
区间DP：石子合并、回文分割
树形DP：树上的最大独立集、树形背包
状态压缩DP：TSP、集合覆盖

10.4 最后的话

动态规划不是“背模板”的算法，而是“找规律”的艺术。当你面对一道新题时，不要急着写代码，先用手工推导小规模情况，观察状态之间的递推关系。多做经典题，慢慢你就会发现，很多DP题的本质都是相通的。

纸上得来终觉浅，绝知此事要躬行。