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 代码JavaclassSolution{publicintmaxProfit(int[]prices){intlenprices.length;int[][]dpnewint[len][4];dp[0][0]-prices[0];dp[0][1]0;dp[0][2]-prices[0];dp[0][3]0;for(inti1;ilen;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(inti1;i2*k;i2){dp[0][i]-prices[0];}含义所有“买入状态”初始化为-prices[0]所有“卖出状态”初始化为0AC 代码JavaclassSolution{publicintmaxProfit(intk,int[]prices){intlenprices.length;int[][]dpnewint[len][2*k1];// 初始化买入状态for(inti1;i2*k;i2){dp[0][i]-prices[0];}for(inti1;ilen;i){for(intj0;j2*k;j2){dp[i][j1]Math.max(dp[i-1][j1],dp[i-1][j]-prices[i]);dp[i][j2]Math.max(dp[i-1][j2],dp[i-1][j1]prices[i]);}}returndp[len-1][2*k];}} 两题对比总结对比项1232 次188k 次状态数量固定 4 个2k 1 个初始化手写循环遍历顺序明确枚举双层循环本质特殊化泛化⏱️ 复杂度分析指标复杂度时间复杂度O(n × k)空间复杂度O(n × k)✅ 一句话总结股票交易次数受限 用奇偶状态表示“买入 / 卖出”k 次交易就是 2k 个状态的状态机 DP。 面试加分点建议记住✅ 为什么用奇偶状态✅ 为什么买入状态初始化为负✅ 为什么是dp[i-1][j-1] - price✅ 和无限次交易的本质区别