我今天分享的是关于动态规划中最有名的一组题目——股票买卖问题。为什么选它？因为它覆盖了大部分DP的建模套路，同时题意又很好理解，非常适合入门。
DP 类型 简要说明 典型例子 1. 线性 DP 当前状态只与前一两个状态有关 斐波那契数列、爬楼梯、打家劫舍 2. 区间 DP 处理“区间”上问题 括号匹配、石子合并 3. 背包 DP 决策是否选某个物品 01 背包、完全背包、多重背包 4. 树形 DP 在树结构上处理最优解 树的直径、选点问题 5. 状压 DP 用二进制压缩状态集合 旅行商问题、Domino 覆盖 6. 记忆化搜索 用递归 + 记忆表解决 DP 问题 所有 DP 都可以转化为搜索 7. 状态机 DP 明确的状态转换模型 买卖股票、任务调度、限制性路径选择 8. 多维 DP 状态有多个维度（例如天数+状态） 买卖股票（第 i 天 + 状态） 9. 插头 DP 用于网格问题、覆盖问题（较高级） Grid覆盖、最小路径覆盖
题目目录：
简单 121. 买卖股票的最佳时机 记录最小值，贪心 or DP 中等 122. 买卖股票的最佳时机 II 多次交易，0/1状态DP 中等 123. 买卖股票的最佳时机 III 最多交易两次，状态维度升级 困难 188. 买卖股票的最佳时机 IV 最多交易 k 次，通用模型 中等 309. 最佳买卖股票时机含冷冻期 状态带冷冻，状态机思想 中等 714. 买卖股票的最佳时机含手续费 状态机 + 手续费处理
什么是状态机 DP？
状态机 DP 本质上是：
把题目的操作过程，抽象成“状态”之间的转移关系，
每种“状态”表示一种特定的场景，
然后我们用 DP 来计算从起点状态走到终点状态的最大/最小值。
它广泛用于 具有阶段性、操作流程清晰的问题，比如股票交易、机器人走格子、任务调度等。
为什么叫“状态机”？
我们借用了**有限状态自动机（Finite State Machine，FSM）**的思想：
- 状态：比如“持有股票”或“未持有股票”
- 操作：比如“买入”、“卖出”、“什么都不做”
- 状态转移图：画出状态之间的合法转移
就像一台机器在不同状态之间切换，直到最终完成任务。
通俗理解：
比如你在打游戏：
你当前是 “未装备武器” 状态；
- 捡到武器后进入 “已装备武器” 状态；
- 打了一场仗后你又 失去武器，回到 “未装备武器” 状态……
这就是“状态”和“状态转移”！
121. 买卖股票的最佳时机
给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
示例 1：
输入：[7,1,5,3,6,4]输出：5解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。 注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。示例 2：
输入：prices = [7,6,4,3,1]输出：0解释：在这种情况下, 没有交易完成, 所以最大利润为 0。提示：
- `1
122. 买卖股票的最佳时机 II
**总而言之，与1的区别就是可以进行任意次交易，但不可同时参与多笔交易 **
详细题目如下：
给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。
在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。
返回 你能获得的 最大 利润 。
示例 1：
输入：prices = [7,1,5,3,6,4]输出：7解释：在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4。随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3。最大总利润为 4 + 3 = 7 。示例 2：
输入：prices = [1,2,3,4,5]输出：4解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4。最大总利润为 4 。示例 3：
输入：prices = [7,6,4,3,1]输出：0解释：在这种情况下, 交易无法获得正利润，所以不参与交易可以获得最大利润，最大利润为 0。提示：
- `1
123. 买卖股票的最佳时机 III
在问题上中，我们可以进行 <= 2 笔交易，这是与问题2的不同
给定一个数组，它的第_ i 个元素是一支给定的股票在第 i _天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 **两笔 **交易。
**注意：**你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1:
输入：prices = [3,3,5,0,0,3,1,4]输出：6解释：在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。 随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。示例 2：
输入：prices = [1,2,3,4,5]输出：4解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。 注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。 因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。示例 3：
输入：prices = [7,6,4,3,1]输出：0解释：在这个情况下, 没有交易完成, 所以最大利润为 0。示例 4：
输入：prices = [1]输出：0提示：
- `1
思路：
三维：
这题关键在于“最多交易两次”，所以我们要引入一个新的维度：交易次数 k（最多 2）
状态定义：
我们用 dp[i][k][j] 表示：
- 第 i 天（从 0 开始）
- 你最多还能进行 k 次交易（k ∈ {0,1,2}）
- 当前是否持股：j = 0 表示未持股，j = 1 表示持股
- dp[i][k][j]：表示在这些条件下的 最大利润
根据上两题的基础，我们可得出如下状态转移方程：
// 不持股dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i]);// 今天不持股 = max(昨天就不持股，昨天持股今天卖出)
// 持股dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i]);// 今天持股 = max(昨天就持股，昨天不持股今天买入一次（交易数-1）)初始化：
dp[0][0][0] = 0; // 第0天不持股0次交易dp[0][1][0] = 0;dp[0][2][0] = 0;
dp[0][0][1] = -INF; // 第0天持股0次交易（非法）dp[0][1][1] = -prices[0]; // 第0天持股1次交易dp[0][2][1] = -prices[0]; // 第0天持股2次交易##### 二维：
既然是状态机dp，那我们首先要确定他现在的状态种类表示
**状态编号** **状态含义** 0 什么也没做 1 第一次买入 2 第一次卖出 3 第二次买入（在第一次卖出之后） 4 第二次卖出（最终状态）
需要注意：dp[i][1]，**表示的是第i天，买入股票的状态，并不是说一定要第i天买入股票，这是很多同学容易陷入的误区**。
**不急，我们一步一步推导：**
达到dp[i][1]状态，有两个具体操作：
- 操作一：第i天买入股票了，那么dp[i][1] = dp[i-1][0] - prices[i]- 操作二：第i天没有操作，而是沿用前一天买入的状态，即：dp[i][1] = dp[i - 1][1]
那么dp[i][1]究竟选 dp[i-1][0] - prices[i]，还是dp[i - 1][1]呢？
一定是选最大的，所以 dp[i][1] = max(dp[i-1][0] - prices[i], dp[i - 1][1]);
同理dp[i][2]也有两个操作：
- 操作一：第i天卖出股票了，那么dp[i][2] = dp[i - 1][1] + prices[i]- 操作二：第i天没有操作，沿用前一天卖出股票的状态，即：dp[i][2] = dp[i - 1][2]
所以dp[i][2] = max(dp[i - 1][1] + prices[i], dp[i - 1][2])
同理可推出剩下状态部分：
dp[i][3] = max(dp[i - 1][3], dp[i - 1][2] - prices[i]);
dp[i][4] = max(dp[i - 1][4], dp[i - 1][3] + prices[i]);
**有了这些不够，还要了解dp数组如何初始化。**
第0天没有操作，这个最容易想到，就是0，即：dp[0][0] = 0;
第0天做第一次买入的操作，dp[0][1] = -prices[0];
第0天做第一次卖出的操作，这个初始值应该是多少呢？
此时还没有买入，怎么就卖出呢？ 其实大家可以理解当天买入，当天卖出，所以dp[0][2] = 0;
第0天第二次买入操作，初始值应该是多少呢？应该不少同学疑惑，第一次还没买入呢，怎么初始化第二次买入呢？
第二次买入依赖于第一次卖出的状态，其实相当于第0天第一次买入了，第一次卖出了，然后再买入一次（第二次买入），那么现在手头上没有现金，只要买入，现金就做相应的减少。
所以第二次买入操作，初始化为：dp[0][3] = -prices[0];
同理第二次卖出初始化dp[0][4] = 0;
以上这些分析完，写出代码是不是就轻轻松松了
**其实，还有另一种方法：压缩 i**
```cppdp[k][j]
// k表示目前进行了几次交易，j表示是否持股状态转移方程因此变为：
dp[k][0] = max(dp[k][0], dp[k][1] + price); // 今天不持股dp[k][1] = max(dp[k][1], dp[k-1][0] - price); // 今天持股（进行了一次买入）注意顺序：
必须从 k = 2 到 k = 1 倒序更新！
为什么？因为：
dp[k][1] = max(dp[k][1], dp[k-1][0] - price);如果你顺序更新，会把dp[k - 1][0] 覆盖成当前的值，导致出错！
代码：
三维：
int maxProfit(vector<int>& prices) { int n = prices.size(); if (n == 0) return 0;
vector<vector<vector<int>>> dp(n, vector<vector<int>>(3, vector<int>(2)));
// 初始化 for (int k = 1; k <= 2; ++k) { dp[0][k][0] = 0; dp[0][k][1] = -prices[0]; }
for (int i = 1; i < n; ++i) { for (int k = 1; k <= 2; ++k) { dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i]); dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i]); } }
return dp[n-1][2][0]; // 最后一天，最多交易两次，不持股}##### 二维：
```cppclass Solution {public: int maxProfit(vector<int>& prices) { int n = prices.size(); if (n == 0) return 0;
vector<vector<int>> dp(n, vector<int>(5, 0));
dp[0][0] = 0; dp[0][1] = -prices[0]; dp[0][2] = 0; dp[0][3] = -prices[0]; dp[0][4] = 0;
for (int i = 1; i < n; ++i) { dp[i][0] = dp[i-1][0]; dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i]); dp[i][2] = max(dp[i-1][2], dp[i-1][1] + prices[i]); dp[i][3] = max(dp[i-1][3], dp[i-1][2] - prices[i]); dp[i][4] = max(dp[i-1][4], dp[i-1][3] + prices[i]); }
return max({dp[n-1][0], dp[n-1][2], dp[n-1][4]}); }};int maxProfit(vector<int>& prices) { vector<vector<int>> dp(3, vector<int>(2, 0)); // 初始化第一天 dp[1][1] = dp[2][1] = -prices[0];
for (int i = 1; i < prices.size(); ++i) { for (int k = 2; k >= 1; --k) { dp[k][0] = max(dp[k][0], dp[k][1] + prices[i]); // 卖出 dp[k][1] = max(dp[k][1], dp[k-1][0] - prices[i]); // 买入 } }
return dp[2][0]; // 最后一天，最多交易两次，不持股}### 还有一件事！
**我们是不是可以把空间压缩为一维，直接用五个变量来代表五个状态岂不美哉！**
s0 什么都没做，或者卖完第二次之后 s1 第一次买入后手里有股票 s2 第一次卖出后，没有股票 s3 第二次买入后，手里有股票 s4 第二次卖出后，没有股票
```cppclass Solution {public: int maxProfit(vector<int>& prices) { int n = prices.size(); if (n == 0) return 0;
int s0 = 0; int s1 = -prices[0]; int s2 = 0; int s3 = -prices[0]; int s4 = 0;
for (int i = 1; i < n; ++i) { s1 = max(s1, s0 - prices[i]); // 第一次买 s2 = max(s2, s1 + prices[i]); // 第一次卖 s3 = max(s3, s2 - prices[i]); // 第二次买 s4 = max(s4, s3 + prices[i]); // 第二次卖 }
return max({s0, s2, s4}); // 最终可以处于这些状态 }};因为最终必须 不持有股票 才是有效的利润，合法的结束状态有
- s0：从未进行过交易
- s2：完成一次交易
- s4：完成两次交易
不包括 s1 和 s3，因为持有股票就意味着还没卖出，收益没落实！
你学费了吗？
这就是状态机DP的精髓之一：
目标 方法 状态少（常数级别） 直接用变量代替数组 状态多（变量 k） 用 dp[k+1][2] 表示交易数和是否持股 状态多 + 节省空间 状态压缩 + 滚动数组/变量
188. 买卖股票的最佳时机 IV
这次我们可以完成 <=K 笔交易了
给你一个整数数组 prices 和一个整数 k ，其中 prices[i] 是某支给定的股票在第 i_ _天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说，你最多可以买 k次，卖 k 次。
**注意：**你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1：
输入：k = 2, prices = [2,4,1]输出：2解释：在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。示例 2：
输入：k = 2, prices = [3,2,6,5,0,3]输出：7解释：在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。 随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。提示：
- `1
309. 最佳买卖股票时机含冷冻期 略
与前几题相比，本题引入了冷冻期概念。卖出股票后，你无法在第二天买入股票
** 当你仍然可以无限次♾️地买卖股票。**
正题如下：⬇️
给定一个整数数组prices，其中第 _ _prices[i] 表示第 _i_ 天的股票价格 。
设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
- 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
**注意：**你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1:
输入: prices = [1,2,3,0,2]输出: 3解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]示例 2:
输入: prices = [1]输出: 0提示：
- `1
714. 买卖股票的最佳时机含手续费
（本次更新移除了冷冻期机制，并添加了手续费bushi）
给定一个整数数组 prices，其中 prices[i]表示第 i 天的股票价格 ；整数 fee 代表了交易股票的手续费用。
你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。
返回获得利润的最大值。
**注意：**这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。
示例 1：
输入：prices = [1, 3, 2, 8, 4, 9], fee = 2输出：8解释：能够达到的最大利润:在此处买入 prices[0] = 1在此处卖出 prices[3] = 8在此处买入 prices[4] = 4在此处卖出 prices[5] = 9总利润: ((8 - 1) - 2) + ((9 - 4) - 2) = 8示例 2：
输入：prices = [1,3,7,5,10,3], fee = 3输出：6提示：
- `1
- dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i]) 解释：今天持股，可以是昨天就持股，或者昨天不持股但今天买了（花钱买）；
初始值：
- dp[0][0] = 0：第 0 天不持股，收益是 0；
- dp[0][1] = -prices[0]：第 0 天持股，花了钱买入股票；
代码：
二维：
#include <iostream>#include <vector>using namespace std;
int maxProfit(vector<int>& prices, int fee) { int n = prices.size(); vector<vector<int>> dp(n, vector<int>(2, 0));
// 初始化 dp[0][0] = 0; // 第 0 天不持股 dp[0][1] = -prices[0]; // 第 0 天持股
for (int i = 1; i < n; ++i) { // 今天不持股 = max(昨天不持股, 昨天持股 + 今天卖出的收益 - 手续费) dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i] - fee);
// 今天持股 = max(昨天持股, 昨天不持股 - 今天买入花的钱) dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i]); }
// 最后一天不能持股才能最大收益 return dp[n-1][0];}#### 一维：
```cpp#include <iostream>#include <vector>using namespace std;
int maxProfit(vector<int>& prices, int fee) { int n = prices.size(); int dp0 = 0; // 不持有股票 int dp1 = -prices[0]; // 持有股票
for (int i = 1; i < n; ++i) { int temp = dp0; dp0 = max(dp0, dp1 + prices[i] - fee); // 卖出时要减去手续费 dp1 = max(dp1, temp - prices[i]); }
return dp0;}总结：
题号 / 名称 问题描述 交易次数限制 特殊限制 状态设计（dp[i][…]) 状态数 DP 维度 说明 121. 买卖股票 I 最多一次交易 1 次 无 dp[i][0/1] 2 个状态 二维 基础模型 122. 买卖股票 II 无限次交易 无限制 无 dp[i][0/1] 2 个状态 二维 贪心更优 123. 买卖股票 III 最多两次交易 2 次 无 dp[i][0~4]（状态机） 5 个状态 二维 状态机 DP 188. 买卖股票 IV 最多 k 次交易 给定 k 无 dp[i][k][0/1] 2k 个状态 三维 正统模型 309. 买卖股票含冷冻期 无限次交易 无限制 卖出后第 2 天才能再买 dp[i][0/1/2]（状态机） 3 个状态 二维 状态机加限制 714. 买卖股票含手续费 无限次交易 无限制 每次交易收手续费 dp[i][0/1] 2 个状态 二维 买入时减手续费
类似题目：
3259. 超级饮料的最大强化能量 - 力扣（LeetCode）
原文发布于 CSDN：动态规划分享之 —— 买卖股票的最佳时机