动态规划（DP）的设计思想与建模范式笔记

导论：DP的顶层战略思想

掌握动态规划，不仅要熟悉其在不同数据结构（线性、树形）上的应用，更要理解其背后更高层次、更抽象的设计思想。这些思想如同战略蓝图，指导我们如何从根本上分析问题，构建递推关系，定义状态的本质。

本笔记将深入剖析四种处于同一抽象层次的核心DP设计范式，它们共同构成了DP问题求解的顶层战略：

划分型DP: 从最后一块的构成方式思考。
区间DP范式: 从最后一次合并操作思考。
背包范式: 从“选择与限制”的角度思考。
状态机DP: 从位置与状态转换的角度思考。

一、划分型DP

这是动态规划中最基础、最经典的范式之一，是许多优化型DP问题的根基。

1. 核心思想

将求解目标 f(n) 的问题，通过分析构成整体的最后一个组成部分，将其不重不漏地划分为 f(n-1), f(n-2), ... 等规模更小的子问题。这种范式的关键在于找到一个清晰的划分标准，确保所有情况都被考虑到，且没有重复。

2. 思维模式

“构成整体的最后一块是什么？”

当我们思考状态 dp[i] 时，我们关注的是构成 i 这个状态的最后一个元素 a[i] 到底扮演了什么角色。这个元素是单独作为一个部分，还是与它之前的元素 a[i-1] 等组合在一起形成了“最后一块”？

3. 战略对比

与状态机DP对比: 状态机DP关注的是在 i 位置的横向情况（例如，当前是持有股票还是卖出状态）。而划分型DP关注的是 1 到 i 这个序列的纵向结构（它是如何由 1 到 i-1 加上第 i 个元素构成的）。

4. 经典范例：最长递增子序列

问题描述

给定一个数字序列，找到它的一个最长的子序列，使得这个子序列中的所有元素单调递增。

建模与分析

战略思想: 采用划分型DP。我们定义 dp[i] 为以序列中第 i 个元素 a[i] 结尾的最长递增子序列的长度。
划分标准: 考虑这个以 a[i] 结尾的最优子序列。它的“最后一块”就是 a[i] 本身。它的“倒数第二块”必然是之前的某个元素 a[j]，其中必须满足 j < i 且 a[j] < a[i]。
状态转移: 为了找到以 a[i] 结尾的最长序列，我们必须找到一个最优的 a[j] 作为它的前驱。因此，我们需要遍历所有 j < i 的位置，在所有满足 a[j] < a[i] 的 j 中，找到那个能提供最长递增子序列的 dp[j]，然后在此基础上加1（加上 a[i] 本身）。
dp[i] = 1 + max({dp[j] | 0 <= j < i 且 a[j] < a[i]})

C++ 实现

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

using namespace std;

int lengthOfLIS(const vector<int>& nums) {
    if (nums.empty()) {
        return 0;
    }
    int n = nums.size();
    vector<int> dp(n, 1); // dp[i]: 以 nums[i] 结尾的最长递增子序列的长度

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < i; ++j) {
            if (nums[j] < nums[i]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
    }

    int maxLength = 0;
    for (int len : dp) {
        maxLength = max(maxLength, len);
    }
    return maxLength;
}

int main() {
    vector<int> nums = {10, 9, 2, 5, 3, 7, 101, 18};
    cout << "最长递增子序列的长度为: " << lengthOfLIS(nums) << endl; // 输出: 4
    return 0;
}

二、区间DP范式

这不仅是一种具体的DP类型，更是一种“由小及大、由内而外”构建最优解的宏观思想。

1. 核心思想

当问题的最终解是关于一个大区间 [1, n] 的最优值时，我们可以反向思考：这个大区间的解，必然是由其内部的若干个不相交的子区间的解，通过最后一次“合并”或“操作”得到的。我们通过枚举这最后一次操作发生的位置来划分问题。

2. 思维模式

“最后一次合并/分割/操作发生在哪里？”

当我们计算 dp[i][j]（代表区间 [i, j] 的解）时，我们思考的是，这个区间是如何形成的？我们通过枚举一个分割点 k (i <= k < j)，将问题分解为求解子区间 dp[i][k] 和 dp[k+1][j]，然后将它们的解合并起来。

3. 战略对比

与划分型DP对比: 划分型DP的递推通常是线性的，从 i-1 推到 i。而区间DP范式的构建顺序是按“区间长度”从小到大递增的，状态转移是二维的。

4. 经典范例：戳气球

问题描述

有 n 个气球，编号为 0 到 n-1。每个气球上都标有一个数字，这些数字存在数组 nums 中。现在要求你戳破所有的气球。每当你戳破一个气球 i 时，你可以获得 nums[left] * nums[i] * nums[right] 个硬币。这里的 left 和 right 代表和 i 相邻的两个气球的序号。注意当你戳破了气球 i 后，气球 left 和气球 right 就变成了相邻的气球。求所能获得硬币的最大数量。

建模与分析

战略思想: 直接思考先戳哪个气球会导致后续状态复杂。我们逆向思考，采用区间DP范式。定义 dp[i][j] 为戳破区间 (i, j) 内所有气球（不包括 i 和 j）所能获得的最大硬币数。
最后一次操作: 考虑 (i, j) 区间内最后被戳破的那个气球 k (i < k < j)。当我们戳破 k 时，(i, k) 和 (k, j) 区间内的所有气球都已经被戳破了。此时，与 k 相邻的气球就是 i 和 j。
- 戳破 k 的得分为 nums[i] * nums[k] * nums[j]。
- 在此之前，戳破 (i, k) 区间的最大得分为 dp[i][k]。
- 在此之前，戳破 (k, j) 区间的最大得分为 dp[k][j]。
状态转移: 我们需要枚举 (i, j) 区间内所有可能的最后被戳破的气球 k，并取其中的最大值。
dp[i][j] = max(dp[i][k] + nums[i] * nums[k] * nums[j] + dp[k][j]) (对于 i < k < j)

C++ 实现

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

using namespace std;

int maxCoins(vector<int>& nums) {
    int n = nums.size();
    nums.insert(nums.begin(), 1);
    nums.push_back(1);

    // dp[i][j]: 戳破 (i, j) 区间内所有气球的最大得分
    vector<vector<int>> dp(n + 2, vector<int>(n + 2, 0));

    // l 是区间长度
    for (int l = 3; l <= n + 2; ++l) {
        // i 是区间起点
        for (int i = 0; i <= (n + 2) - l; ++i) {
            int j = i + l - 1;
            // k 是最后戳破的气球
            for (int k = i + 1; k < j; ++k) {
                int score = dp[i][k] + nums[i] * nums[k] * nums[j] + dp[k][j];
                dp[i][j] = max(dp[i][j], score);
            }
        }
    }
    return dp[0][n + 1];
}

int main() {
    vector<int> nums = {3, 1, 5, 8};
    cout << "能获得的最大硬币数量为: " << maxCoins(nums) << endl; // 输出: 167
    return 0;
}

三、背包范式

这是一种极其重要的泛化思想，它将许多看似不同的问题归结为统一的“选择与限制”模型。

1. 核心思想

将问题抽象为：在一系列给定的“物品”（选项、元素）中进行决策，每个决策会消耗某些“资源”（如重量、成本），并产生一定的“价值”（收益、计数值）。目标是在给定的资源“容量”限制内，做出决策，以最大化（或最小化）总价值。

2. 思维模式

“对于当前这件物品，我选还是不选？”

当考虑 dp[i][j]（即考虑前 i 件物品，在容量为 j 的限制下）时，我们的决策焦点完全集中在第 i 件物品上：
1. 不选择它: 那么问题直接转化为：考虑前 i-1 件物品，在容量 j 的限制下的解，即 dp[i-1][j]。
2. 选择它: 那么我们需要为它预留 weight[i] 的容量，然后用剩余的容量 j - weight[i] 去解决前 i-1 件物品的问题，即 dp[i-1][j - weight[i]]。

3. 战略对比

与状态机DP对比: 状态机DP的转移通常是横向的，从 i-1 位置的某个状态转移到 i 位置的某个状态，位置本身没有“选/不选”的概念。而背包范式的核心就是每个物品的“选/不选”决策，状态转移通常是跨行的（从 i-1 行转移到 i 行）。

4. 经典范例：分割等和子集

问题描述

给你一个只包含正整数的非空数组 nums。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

建模与分析

战略思想: 这个问题可以转化为背包问题。
转化: 如果数组可以被分割成两个和相等的子集，那么每个子集的和必然是整个数组总和 sum 的一半。因此，问题转化为：是否可以在数组 nums 中，挑选出若干个元素，使得它们的和恰好等于 sum / 2？
背包模型:
- 物品: nums 数组中的每个数字 num。
- 背包容量: target = sum / 2。
- 物品重量: 每个数字 num 的值。
- 目标: 判断是否存在一种装法，刚好能装满背包。这是一个可行性0/1背包问题。
- 状态: dp[j] 表示容量为 j 的背包是否能被装满（布尔值）。

C++ 实现

#include <iostream>
#include <vector>
#include <numeric>

using namespace std;

bool canPartition(const vector<int>& nums) {
    int sum = accumulate(nums.begin(), nums.end(), 0);

    // 如果总和是奇数，不可能平分
    if (sum % 2 != 0) {
        return false;
    }

    int target = sum / 2;
    // dp[j] 表示容量为 j 的背包是否能被装满
    vector<bool> dp(target + 1, false);
    dp[0] = true;

    for (int num : nums) {
        for (int j = target; j >= num; --j) {
            // 如果容量为 j-num 的背包能被装满，那么放入 num 后，
            // 容量为 j 的背包也能被装满
            dp[j] = dp[j] || dp[j - num];
        }
    }

    return dp[target];
}

int main() {
    vector<int> nums = {1, 5, 11, 5};
    cout << "是否可以分割: " << (canPartition(nums) ? "是" : "否") << endl; // 输出: 是
    return 0;
}

四、状态机DP

这种范式通过对问题的“状态”进行精细的分类和定义，来处理那些具有复杂、离散的模式或规则的问题。

1. 核心思想

将问题的求解过程看作一个有限状态自动机的运行过程。在序列的每一个位置 i，系统都可能处于几种预先定义好的、互斥的“状态”之一。我们通过DP计算到达每个位置的每种状态的可能性或最优值。

2. 思维模式

“在当前这个位置，我处于哪种可能的状态？”

我们的思考焦点是位置 i 本身。根据题目规则，定义出在 i 位置所有可能存在的、对后续决策有影响的“情况”（即状态）。然后，分析 i 位置的某个状态 S1，可以由 i-1 位置的哪些状态 S_prev 经过一步操作转移而来。

3. 战略对比

与划分型/背包范式对比: 这两种范式通常关注“元素”本身（是否作为结尾、是否被选择），而状态机DP更关注“位置”本身所处的上下文环境（如持有股票、处于冷却期等）。

4. 经典范例：买卖股票的最佳时机含冷冻期

问题描述

给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格。设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易：
1. 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
2. 卖出股票后，你无法在第二天买入股票 (即 1 天冷冻期)。

建模与分析

战略思想: 在每一天，我们的“状态”是不同的。采用状态机DP。
状态定义: 对于第 i 天，我们定义三种可能的状态：
1. dp[i][0]: 持有股票状态。当天结束时，我们手中有一支股票。
2. dp[i][1]: 不持有股票，且处于冷冻期。当天我们刚刚卖出了股票。
3. dp[i][2]: 不持有股票，且不处于冷冻期。当天我们什么也没做，或者冷冻期已过。
状态转移:
- dp[i][0] (持有):
  - 可能来自昨天就持有：dp[i-1][0]。
  - 可能来自昨天是非冷冻期，今天买入：dp[i-1][2] - prices[i]。
    dp[i][0] = max(dp[i-1][0], dp[i-1][2] - prices[i])
- dp[i][1] (冷冻期):
  - 只能来自昨天持有，今天卖出：dp[i-1][0] + prices[i]。
- dp[i][2] (非冷冻期):
  - 可能来自昨天就是非冷冻期：dp[i-1][2]。
  - 可能来自昨天是冷冻期，今天冷冻期结束：dp[i-1][1]。
    dp[i][2] = max(dp[i-1][2], dp[i-1][1])
最终答案: 最大利润必然是在最后一天不持有股票的状态下取得，即 max(dp[n-1][1], dp[n-1][2])。

C++ 实现

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

using namespace std;

int maxProfit(const vector<int>& prices) {
    int n = prices.size();
    if (n <= 1) {
        return 0;
    }

    // dp[i][0]: 持有
    // dp[i][1]: 不持有，冷冻期
    // dp[i][2]: 不持有，非冷冻期
    vector<vector<int>> dp(n, vector<int>(3, 0));

    // 初始化
    dp[0][0] = -prices[0];
    dp[0][1] = 0;
    dp[0][2] = 0;

    for (int i = 1; i < n; ++i) {
        dp[i][0] = max(dp[i - 1][0], dp[i - 1][2] - prices[i]);
        dp[i][1] = dp[i - 1][0] + prices[i];
        dp[i][2] = max(dp[i - 1][2], dp[i - 1][1]);
    }

    return max(dp[n - 1][1], dp[n - 1][2]);
}

int main() {
    vector<int> prices = {1, 2, 3, 0, 2};
    cout << "最大利润为: " << maxProfit(prices) << endl; // 输出: 3
    return 0;
}