企业官网建设流程全解析

LeetCode 188 & 123：股票买卖问题（限制交易次数）—— 联合题解 ✅

📌 题目列表

📖 内容概要

给定一个数组prices，其中prices[i]表示第i天的股价。
你最多可以完成k 笔交易（一次买入 + 一次卖出算一笔交易）。
求能获得的最大利润。

✅ 动态规划
✅ 状态机模型
✅ 面试 Hard 题

💡 核心思想（非常重要）

一、状态设计（统一）

dp[i][j]

含义：

• i：第i天
• 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）

状态含义

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];}}

🔍 两题对比总结

⏱️ 复杂度分析

✅ 一句话总结

股票交易次数受限 = 用奇偶状态表示“买入 / 卖出”，k 次交易就是 2k 个状态的状态机 DP。

📌 面试加分点（建议记住）

• ✅ 为什么用奇偶状态？
• ✅ 为什么买入状态初始化为负？
• ✅ 为什么是dp[i-1][j-1] - price？
• ✅ 和无限次交易的本质区别