LeetCode 188 123：股票买卖问题（限制交易次数）—— 联合题解
LeetCode 188 & 123：股票买卖问题（限制交易次数）—— 联合题解 ✅
📌 题目列表
| 题号 | 题目 | 交易限制 |
|---|---|---|
| 123 | 买卖股票的最佳时机 III | 最多2 次 |
| 188 | 买卖股票的最佳时机 IV | 最多k 次 |
📖 内容概要
给定一个数组prices，其中prices[i]表示第i天的股价。
你最多可以完成k 笔交易（一次买入 + 一次卖出算一笔交易）。
求能获得的最大利润。
✅ 动态规划
✅ 状态机模型
✅ 面试 Hard 题
💡 核心思想（非常重要）
一、状态设计（统一）
dp[i][j]含义：
i：第i天j：当前处于第几次交易的哪个阶段
| j 的奇偶性 | 含义 |
|---|---|
| 奇数 | 持有股票（买入后） |
| 偶数 | 不持有股票（卖出后） |
二、状态数量
- 最多
k次交易 - 共
2 × k + 1个状态
🔁 状态转移（核心）
1️⃣ 持有股票（奇数状态）
dp[i][j]=max(dp[i-1][j],// 继续持有dp[i-1][j-1]-prices[i]// 在第 i 天买入)2️⃣ 不持有股票（偶数状态）
dp[i][j]=max(dp[i-1][j],// 继续不持有dp[i-1][j-1]+prices[i]// 在第 i 天卖出)✅ 123 题：最多 2 次交易（k = 2）
状态含义
| 状态 | 含义 |
|---|---|
| 0 | 第 1 次买入 |
| 1 | 第 1 次卖出 |
| 2 | 第 2 次买入 |
| 3 | 第 2 次卖出 |
AC 代码（Java）
classSolution{publicintmaxProfit(int[]prices){intlen=prices.length;int[][]dp=newint[len][4];dp[0][0]=-prices[0];dp[0][1]=0;dp[0][2]=-prices[0];dp[0][3]=0;for(inti=1;i<len;i++){dp[i][0]=Math.max(dp[i-1][0],-prices[i]);dp[i][1]=Math.max(dp[i-1][1],dp[i-1][0]+prices[i]);dp[i][2]=Math.max(dp[i-1][2],dp[i-1][1]-prices[i]);dp[i][3]=Math.max(dp[i-1][3],dp[i-1][2]+prices[i]);}returndp[len-1][3];}}✅ 188 题：最多 k 次交易（通用解）
初始化（非常关键）
for(inti=1;i<2*k;i+=2){dp[0][i]=-prices[0];}含义：
- 所有“买入状态”初始化为
-prices[0] - 所有“卖出状态”初始化为
0
AC 代码（Java）
classSolution{publicintmaxProfit(intk,int[]prices){intlen=prices.length;int[][]dp=newint[len][2*k+1];// 初始化买入状态for(inti=1;i<2*k;i+=2){dp[0][i]=-prices[0];}for(inti=1;i<len;i++){for(intj=0;j<2*k;j+=2){dp[i][j+1]=Math.max(dp[i-1][j+1],dp[i-1][j]-prices[i]);dp[i][j+2]=Math.max(dp[i-1][j+2],dp[i-1][j+1]+prices[i]);}}returndp[len-1][2*k];}}🔍 两题对比总结
| 对比项 | 123（2 次） | 188（k 次） |
|---|---|---|
| 状态数量 | 固定 4 个 | 2k + 1 个 |
| 初始化 | 手写 | 循环 |
| 遍历顺序 | 明确枚举 | 双层循环 |
| 本质 | 特殊化 | 泛化 |
⏱️ 复杂度分析
| 指标 | 复杂度 |
|---|---|
| 时间复杂度 | O(n × k) |
| 空间复杂度 | O(n × k) |
✅ 一句话总结
股票交易次数受限 = 用奇偶状态表示“买入 / 卖出”，k 次交易就是 2k 个状态的状态机 DP。
📌 面试加分点（建议记住）
- ✅ 为什么用奇偶状态？
- ✅ 为什么买入状态初始化为负？
- ✅ 为什么是
dp[i-1][j-1] - price？ - ✅ 和无限次交易的本质区别