买卖股票 - 个人博客

一、状态机模型思想对于股票问题，我们通常定义两种状态：
● 持有状态 (holding)：手上持有股票。
● 空仓状态 (not holding)：手上不持有股票。在某些题型中，还需要考虑交易次数（例如最多进行 (k) 次交易）或者其他约束（如冷冻期、手续费）。状态转移方程一般写法假设 $dp[i][k][0]$表示第 i 天、最多完成 k 次交易，且不持有股票的最大收益； $dp[i][k][1]$表示第 i 天、最多完成 k 次交易，且持有股票的最大收益。
常用的状态转移方程为：
● 转移到不持有状态 $dp[i][k][0] = \max(dp[i-1][k][0],\ dp[i-1][k][1] + \text{prices}[i])$ 解释：要么前一天就不持有，今天不操作；要么前一天持有，今天卖出（注意卖出完成一次交易）。 ● 转移到持有状态 $dp[i][k][1] = \max(dp[i-1][k][1],\ dp[i-1][k-1][0] - \text{prices}[i])$ 解释：要么前一天就持有，今天不操作；要么前一天不持有，今天买入（交易次数加1）。附加条件会在状态转移时加以调整。二、各大题型及其状态转移方程

买卖股票 I 题意：只允许进行一次交易。思路：只需求出一个最低买入价与最高卖出价之差。 https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/ 状态与转移这里可以直接用贪心方法，但也可以构造 DP：
● 定义 ( dp[i][0] ) 为第 (i) 天不持有股票时的最大收益。
● 定义 ( dp[i][1] ) 为第 (i) 天持有股票时的最大收益。初始状态： ● $dp[0][0] = 0$ ● $dp[0][1] = -\text{prices}[0]$ 转移方程（只允许一次买卖，因此买入后不能再次买入）： $dp[i][0] = \max(dp[i-1][0],\ dp[i-1][1] + \text{prices}[i])$ $dp[i][1] = \max(dp[i-1][1],\ -\text{prices}[i])$ 示例代码（Java）： class Solution { public int maxProfit(int[] prices) { int n = prices.length; if(n == 0) return 0; int dp0 = 0, dp1 = -prices[0]; for (int i = 1; i < n; i++) { dp0 = Math.max(dp0, dp1 + prices[i]); dp1 = Math.max(dp1, -prices[i]); } return dp0; } } class Solution { public int maxProfit(int[] prices) { int n = prices.length; if (n == 0) return 0;
```
 int min = prices[0];
 int max = 0;
 for (int i = 1; i < n; i++) {
     max = Math.max(max, prices[i] - min);
     min = Math.min(min, prices[i]);
 }

 return max;
```
} }
买卖股票 II 题意：可以进行无限次交易，但不能同时持有多支股票。思路：每天都可以选择买入或卖出。 https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/description/ 状态与转移初始状态： ● $dp[0][0] = 0$ ● $dp[0][1] = -\text{prices}[0]$ 转移方程： $dp[i][0] = \max(dp[i-1][0],\ dp[i-1][1] + \text{prices}[i])$ $dp[i][1] = \max(dp[i-1][1],\ dp[i-1][0] - \text{prices}[i])$ 示例代码（Java）： class Solution { public int maxProfit(int[] prices) { int n = prices.length; if (n == 0) return 0;
```
 int[][] dp = new int[n][2];
 dp[0][0] = 0;
 dp[0][1] = -prices[0];

 for (int i = 1; i < n; i++) {
     //当前未持有的最大利润 = max(前一天未持有，前一天持有+今天卖了)
     dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
     //当前持有的最大利润 = max(前一天也持有，前一天未持有+今天买入（买入扣钱）)
     dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
 }
 //最后一天一定是未持有利润最大，因为持有卖不了纯亏钱
 return dp[n - 1][0];
```
} }
买卖股票 III 题意：最多进行两次交易。思路：加入交易次数的维度 ( k )，状态转移参考状态定义 ( dp[i][k][0/1] )。
买卖股票的最佳时机 III - 力扣（LeetCode）状态与转移 ● $dp[i][k][0] = \max(dp[i-1][k][0],\ dp[i-1][k][1] + \text{prices}[i])$ ● $dp[i][k][1] = \max(dp[i-1][k][1],\ dp[i-1][k-1][0] - \text{prices}[i])$ 注意：交易次数 ( k ) 从 1 开始。示例代码（Java）： class Solution { public int maxProfit(int[] prices) { int n = prices.length; if (n <= 1) return 0;

// dp[i][k][0]：第 i 天进行 k 次交易且未持有股票的最大收益 // dp[i][k][1]：第 i 天进行 k 次交易且持有股票的最大收益 int[][][] dp = new int[n][3][2];

// 初始化第 0 天的状态 for (int k = 0; k <= 2; k++) { dp[0][k][0] = 0; dp[0][k][1] = -prices[0]; // 第 0 天买入股票 }

// 遍历每一天 for (int i = 1; i < n; i++) { for (int k = 1; k <= 2; k++) { // 最多交易 2 次 // 未持有股票 dp[i][k][0] = Math.max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i]); // 持有股票 dp[i][k][1] = Math.max(dp[i - 1][k][1], dp[i - 1][k - 1][0] - prices[i]); } }

return dp[n - 1][2][0]; // 最后一天，最多交易 2 次，未持有股票的最大收益 } }

买卖股票 IV 题意：最多进行 ( k ) 次交易。思路：与股票 III 类似，但交易次数为参数，可动态变化。状态转移方程与股票 III 类似，只不过循环 ( k ) 的上限为题目给定的 ( k ) 值。 https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iv/ 状态与转移 ● $dp[i][j][0] = \max(dp[i-1][j][0],\ dp[i-1][j][1] + \text{prices}[i])$ ● $dp[i][j][1] = \max(dp[i-1][j][1],\ dp[i-1][j-1][0] - \text{prices}[i])$ 示例代码（Java）： class Solution { public int maxProfit(int k, int[] prices) { int n = prices.length; if (n <= 1) return 0;

 // dp[i][k][0]：第 i 天进行 k 次交易且未持有股票的最大收益
 // dp[i][k][1]：第 i 天进行 k 次交易且持有股票的最大收益
 int[][][] dp = new int[n][k + 1][2];

 // 初始化第 0 天的状态
 for (int i = 0; i <= k; i++) {
     dp[0][i][0] = 0;
     dp[0][i][1] = -prices[0]; // 第 0 天买入股票
 }

 // 遍历每一天
 for (int i = 1; i < n; i++) {
     for (int j = 1; j <= k; j++) { // 最多交易 k 次
         // 未持有股票
         dp[i][j][0] = Math.max(dp[i - 1][j][0], dp[i - 1][j][1] + prices[i]);
         // 持有股票
         dp[i][j][1] = Math.max(dp[i - 1][j][1], dp[i - 1][j - 1][0] - prices[i]);
     }
 }

 return dp[n - 1][k][0]; // 最后一天，最多交易 k 次，未持有股票的最大收益

} }

带冷冻期的股票题意：买卖股票后第二天不能买入，即存在冷冻期。思路：状态转移时需考虑冷冻期的约束。
https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-cooldown/ 状态与转移假设： ● $dp[i][0]$表示第 (i) 天未持有股票的最大收益
● $dp[i][1]$表示第 (i) 天持有股票的最大收益初始状态： ● $dp[0][0] = 0$ ● $dp[0][1] = -\text{prices}[0]$ 转移方程： ● 卖出股票时： $dp[i][0] = \max(dp[i-1][0],\ dp[i-1][1] + \text{prices}[i])$ ● 买入股票时需要跳过前一天（冷冻期）： $dp[i][1] = \max(dp[i-1][1],\ dp[i-2][0] - \text{prices}[i])$ 注意：当 ( i-2 < 0 ) 时需特殊处理。示例代码（Java）： class Solution { public int maxProfit(int[] prices) { int n = prices.length; if (n <= 1) return 0;
```
 int[][] dp = new int[n][2];
 dp[0][0] = 0;
 dp[0][1] = -prices[0];

 for (int i = 1; i < n; i++) {
     dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
     if (i > 2)
         dp[i][1] = Math.max(dp[i - 1][1], dp[i - 2][0] - prices[i]);
     else
         //如果i==1，那么只能在第一天买入或者在第二天买入
         dp[i][1] = Math.max(dp[i - 1][1], -prices[i]);
 }

 return dp[n - 1][0];
```
} }
带手续费的股票题意：每笔交易需要扣除一定手续费。思路：在卖出时扣除手续费即可。
状态与转移初始状态： ● $dp[0][0] = 0$ ● $dp[0][1] = -\text{prices}[0]$ 转移方程： $dp[i][0] = \max(dp[i-1][0],\ dp[i-1][1] + \text{prices}[i] - \text{fee})$ $dp[i][1] = \max(dp[i-1][1],\ dp[i-1][0] - \text{prices}[i])$ 示例代码（Java）： class Solution { public int maxProfit(int[] prices, int fee) { int n = prices.length; if (n == 0) return 0;
```
 int[][] dp = new int[n][2];
 dp[0][0] = 0;
 dp[0][1] = -prices[0];

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

 return dp[n - 1][0];
```
} }

总结

核心思想利用状态机/动态规划记录每天的“持有”与“空仓”状态，同时根据题目要求增加交易次数、冷冻期、手续费等约束。
状态转移公式
○ 卖出操作：收益 = 前一天持有状态 + 当前卖出价格（有时扣除手续费）
○ 买入操作：收益 = 前一天空仓状态 - 当前买入价格（有时受冷冻期约束）
代码优化对于状态仅依赖前一天的情况，可以用滚动数组或变量优化空间复杂度。