动态规划

动态规划是一种常见且多变的编程思想。DP 一般用来解决：

• 求最大/最小值。
• 求可行的方案数。

通常，要应用 DP 做题，分为以下步骤：

1. 设计 DP 状态。DP 状态一般是问题的局部最优解，利用局部最优解推导全局最优解是 DP 的核心。
2. 推导状态转移方程。此步，一般是假设某些状态已经求出，然后递推新的 DP状态。又细分：
   1. 先推导大多数情况下的转移方程，然后仔细考虑边界情况。
   2. 一般要使用 $min()$、$max()$ 来选择更优情况。
3. 考虑边界情况，适应于具体问题。

DP 状态是张量，一维到四维甚至以上都有。还有树状 DP。 的时间复杂度从 $O(n)$ 到 $O(n^3)$ 不等。

本文将试着总结一些常见的 DP 思路。

0/1 背包

十分经典。题目描述如下：

你有一个容量为 $n$ 的背包，现在告诉你 $m$ 件物品，每件物品有两个属性：体积 $w_i$ 和价值 $v_i$。

你的目标是：求背包最多能装下多少价值的物品。

之所以叫“0/1”，是因为对于每个物品只有“选”和“不选”两个状态。

状态设计

$dp[i][j]$ 定义为：从物品 $[0,i]$ 中选择，背包的最大容量为 $j$，能达到的最大价值。

转移方程

假设我们已经求完 $dp[i-1][...]$，现在我们开始考虑第 $i$ 个物品，则有：

$$dp[i][j]=max(dp[i][j], dp[i-1][j-w_i]+v_i)$$

我们将按照这样的顺序转移状态：

dp[1][0] -> dp[1][1] -> dp[1][2] -> ... -> dp[1][m] -> 
dp[2][0] -> dp[2][1] -> dp[2][2] -> ... -> dp[2][m] -> 
... -> dp[n][m] -> 结束

实际代码

包含了对边界情况的考虑。

dp[0][0] = 0;
for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
        if (j - w[i] < 0) continue;
        dp[i][j] = max(dp[i][j], dp[i][j - w[i]] + v[i]);
    }
}
ans = dp[n - 1][m];

多步决策求方案数

以洛谷 P1044 为例：

依次有 $\{1,2,3,...,N\}$ 这 $N$ 个数字要入栈，求出栈顺序的总数。

实际上求的就是：求所有合法的、由 $\{\text{push},\text{pop}\}$ 组成的序列总数。下面称此序列为“操作序列”。容易得到，每一个操作序列都可以得到一个独一无二的输出序列。