动态规划基础：状态、转移与计算顺序｜算法讲义

问题#

动态规划不是某一段固定代码，而是一种组织重复子问题的方法。面对一道 DP 题，应依次写清楚：

状态：dp[...] 精确表示什么，是否包含当前位置？
转移：当前状态由哪些更小状态得到？
初始状态：最小问题的答案是什么？不可达状态用什么表示？
计算顺序：计算当前状态时，它依赖的状态是否已经得到？
最终答案：是某一个状态，还是一组状态的最大值或总和？

动态规划通常要求问题具有重叠子问题和最优子结构；状态还必须满足无后效性，即未来转移只需要读取状态中保存的信息，不再依赖此前的完整决策历史。

核心思想与不变量#

例一：走楼梯——计数型线性 DP#

每次走 $1$ 或 $2$ 阶，求到达第 $n$ 阶的方法数。定义：

dp[i]=\text{恰好到达第 }i\text{ 阶的方法数}.

到达 $i$ 的最后一步只可能来自 $i-1$ 或 $i-2$ ，因此：

dp[i]=dp[i-1]+dp[i-2],\qquad dp[0]=1,\ dp[1]=1.

这里 dp[0] = 1 表示“什么都不做”这一种空方案，它让后续转移保持统一。按 $i$ 从小到大计算时，不变量是：循环开始处理 $i$ 前，所有更小阶数的方法数已经正确。

例二：最大连续子段和——最优化型线性 DP#

定义：

dp[i]=\text{必须以 }a_i\text{ 结尾的非空连续子段最大和}.

最优子段要么只含 $a_i$ ，要么把 $a_i$ 接在以 $a_{i-1}$ 结尾的最优子段后面：

dp[i]=\max(a_i,dp[i-1]+a_i).

全局答案是 $\max_i dp[i]$ ，而不是 dp[n-1]。因为当前状态只依赖前一个状态，可以把 DP 数组压缩为一个变量；若还要恢复区间，则额外记录当前起点和全局最优端点。

记忆化搜索与递推#

记忆化搜索从目标状态向依赖状态递归，第一次求出后缓存结果；递推则按依赖图的拓扑顺序主动计算所有需要的状态。两者使用同一条转移，选择标准主要是：

状态几乎都会被访问、顺序清楚：优先递推；
状态稀疏、只有少部分可达：记忆化搜索可能更自然；
递归深度可能很大：递推更安全。

例三：最少硬币找零——完全选择型 DP#

给定若干正整数面额，可以无限次使用每种硬币，求恰好组成金额 $K$ 所需的最少硬币数。定义：

dp[x]=\text{恰好组成金额 }x\text{ 所需的最少硬币数}.

最后一枚硬币若为 $c$ ，此前必须恰好组成 $x-c$ ，因此：

dp[x]=\min_{c\le x}\bigl(dp[x-c]+1\bigr).

初始化 dp[0] = 0，其余状态为不可达。金额从小到大枚举，因为计算 dp[x] 时，所有 dp[x-c] 都应已经完成；同一种硬币能够在不同金额的转移中重复使用。若最终状态仍不可达，则没有找零方案。

循环不变量是：开始处理金额 $x$ 前，所有小于 $x$ 的金额已经得到最优答案或被正确标记为不可达。

复杂度#

走楼梯和最大连续子段和都只扫描一次，时间为 $O(n)$ 。若保存整个 dp 数组，空间为 $O(n)$ ；只保留转移所需的最近状态时，空间为 $O(1)$ 。若面额种类数为 $C$ 、目标金额为 $K$ ，最少硬币找零的时间为 $O(KC)$ 、空间为 $O(K)$ 。记忆化搜索的复杂度一般是“可达状态数 × 每个状态的转移数”。

C++17 模板#

下面的程序同时给出计数型线性 DP 和带方案恢复的最优化型线性 DP。走楼梯的结果可能很大，模板用 mod 控制取模；传入 mod = 0 表示不取模，但仍须自行保证不溢出 long long。

#include <algorithm>
#include <iostream>
#include <stdexcept>
#include <vector>

using namespace std;

long long stair_ways(int n, long long mod = 0) {
    if (n < 0) return 0;
    if (n == 0) return 1;

    long long previous_two = 1; // dp[0]
    long long previous_one = 1; // dp[1]
    for (int i = 2; i <= n; ++i) {
        long long current;
        if (mod > 0) {
            current = (previous_one + previous_two) % mod;
        } else {
            current = previous_one + previous_two;
        }
        previous_two = previous_one;
        previous_one = current;
    }
    return previous_one;
}

struct SubarrayAnswer {
    long long sum;
    int left;
    int right; // 闭区间 [left, right]
};

SubarrayAnswer maximum_subarray(const vector<long long>& a) {
    if (a.empty()) throw invalid_argument("array must be non-empty");

    long long ending_sum = a[0];
    int ending_left = 0;
    SubarrayAnswer answer{a[0], 0, 0};

    for (int i = 1; i < static_cast<int>(a.size()); ++i) {
        if (ending_sum + a[i] < a[i]) {
            ending_sum = a[i];
            ending_left = i;
        } else {
            ending_sum += a[i];
        }

        if (ending_sum > answer.sum) {
            answer = {ending_sum, ending_left, i};
        }
    }
    return answer;
}

int main() {
    cout << "ways(5) = " << stair_ways(5) << '\n';

    vector<long long> values = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    SubarrayAnswer answer = maximum_subarray(values);
    cout << "maximum sum = " << answer.sum
         << ", interval = [" << answer.left << ", " << answer.right << "]\n";
    return 0;
}

独立模板：最少硬币找零#

模板同时保存最后选择的硬币，以恢复一组最优方案。它要求目标金额非负、所有面额为正；返回 count = -1 表示目标不可达。

#include <algorithm>
#include <iostream>
#include <limits>
#include <stdexcept>
#include <vector>

using namespace std;

struct CoinChangeAnswer {
    int count;
    vector<int> coins;
};

CoinChangeAnswer minimum_coin_change(int target, const vector<int>& denomination) {
    if (target < 0) throw invalid_argument("target must be non-negative");
    for (int coin : denomination) {
        if (coin <= 0) throw invalid_argument("coin values must be positive");
    }

    const int infinity = numeric_limits<int>::max() / 4;
    vector<int> dp(target + 1, infinity);
    vector<int> last_coin(target + 1, -1);
    dp[0] = 0;

    for (int amount = 1; amount <= target; ++amount) {
        for (int coin : denomination) {
            if (coin <= amount && dp[amount - coin] != infinity
                && dp[amount - coin] + 1 < dp[amount]) {
                dp[amount] = dp[amount - coin] + 1;
                last_coin[amount] = coin;
            }
        }
    }

    if (dp[target] == infinity) return {-1, {}};

    vector<int> used;
    for (int amount = target; amount > 0; amount -= last_coin[amount]) {
        used.push_back(last_coin[amount]);
    }
    return {dp[target], used};
}

int main() {
    CoinChangeAnswer answer = minimum_coin_change(63, {1, 5, 10, 21, 25});
    cout << "minimum coins = " << answer.count << "\ncoins:";
    for (int coin : answer.coins) cout << ' ' << coin;
    cout << '\n';
    return 0;
}

示例#

模板输出：

ways(5) = 8
maximum sum = 6, interval = [3, 6]

最大子段是 4 -1 2 1。处理到元素 -3 时，以它结尾的最优和为 -2；处理到 4 时，丢弃负贡献并从当前位置重新开始，之后逐步扩展到答案区间。

找零模板对金额 63 输出 3 枚硬币，恢复方案为 21 21 21。若面额改为 {4, 6}、目标为 5，则返回 count = -1；目标为 0 时答案为 0 枚硬币。

易错点#

状态定义缺少“恰好”“至多”“必须以某处结尾”等限定词，会让转移和答案位置产生歧义。
计数 DP 的空方案常是 1；最优化 DP 的不可达状态通常应初始化为正无穷或负无穷，不能一律填 0。
最大连续子段和要求非空时，全负数组的答案是最大的单个元素，不能把答案初始化为 0。
空间压缩前先检查依赖方向；覆盖了仍会被本轮使用的状态会改变模型。
方案数即使取模，两个操作数相加前也可能溢出；模数和数据更大时需使用更宽类型或安全加法。
记忆化搜索要区分“尚未计算”和“答案恰好等于默认值”这两种状态。
找零 DP 不能从不可达的 dp[x-c] 转移；面额为 0 或负数还会破坏金额递增的依赖顺序。
“最少硬币”允许重复使用面额；若每枚硬币只能用一次，模型会变成 0/1 背包，遍历顺序不同。

问题#