LeetCode 121 122：股票买卖问题（DP 对比题解）✅

LeetCode 121 & 122：股票买卖问题（DP 对比题解）✅

📌 题目列表

📖 内容概要

给定一个数组prices，其中prices[i]是第i天的股票价格。
你需要选择买入和卖出时机，使利润最大。

• 121：只能买卖一次
• 122：可以多次买卖（同一天不能同时买卖）

✅ 动态规划
✅ 状态机思想
✅ 面试高频题

💡 统一 DP 定义（两题通用）

dp[i][0]=第 i 天结束时，不持有股票的最大利润 dp[i][1]=第 i 天结束时，持有股票的最大利润

🔁 状态转移（核心）

不持有股票dp[i][0]

dp[i][1]=max(前一天就不持有,前一天持有+今天卖出)

✅ 两题完全一致

持有股票dp[i][1]

✅这是两道题的唯一区别

✅ 121 题：只能买卖一次（AC 代码）

classSolution{publicintmaxProfit(int[]prices){intlen=prices.length;int[][]dp=newint[len][2];dp[0][0]=0;// 不持股dp[0][1]=-prices[0];// 持股for(inti=1;i<len;i++){dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]+prices[i]);dp[i][1]=Math.max(dp[i-1][1],-prices[i]);// 只能买一次}returndp[len-1][0];}}

✅ 关键点

• 第二次买入时：
  • 之前不能有利润
  • 只能是-prices[i]

✅ 122 题：可以无限交易（AC 代码）

classSolution{publicintmaxProfit(int[]prices){intlen=prices.length;int[][]dp=newint[len][2];dp[0][0]=0;dp[0][1]=-prices[0];for(inti=1;i<len;i++){dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]+prices[i]);dp[i][1]=Math.max(dp[i-1][1],dp[i-1][0]-prices[i]);}returndp[len-1][0];}}

✅ 关键点

• 再次买入时：
  • 使用的是之前不持股的最大利润

🔍 两题核心差异对比

⏱️ 复杂度分析

🚀 空间优化（通用）

inthold=-prices[0];intcash=0;for(inti=1;i<prices.length;i++){intprevCash=cash;cash=Math.max(cash,hold+prices[i]);hold=Math.max(hold,prevCash-prices[i]);}returncash;

✅ 一句话总结

121 限制“只能买一次”，122 允许“反复买卖”，区别仅在于持有股票的转移方程。