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

LeetCode 121 122股票买卖问题DP 对比题解✅ 题目列表题号题目限制121买卖股票的最佳时机I只能交易1 次122买卖股票的最佳时机II可以交易无限次 内容概要给定一个数组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]题目转移方程含义121max(dp[i-1][1], -prices[i])只能买一次122max(dp[i-1][1], dp[i-1][0] - prices[i])可以反复买✅这是两道题的唯一区别✅ 121 题只能买卖一次AC 代码classSolution{publicintmaxProfit(int[]prices){intlenprices.length;int[][]dpnewint[len][2];dp[0][0]0;// 不持股dp[0][1]-prices[0];// 持股for(inti1;ilen;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){intlenprices.length;int[][]dpnewint[len][2];dp[0][0]0;dp[0][1]-prices[0];for(inti1;ilen;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];}}✅ 关键点再次买入时使用的是之前不持股的最大利润 两题核心差异对比对比项121一次122无限次是否可多次买卖❌✅持有状态转移-prices[i]dp[i-1][0] - prices[i]DP 含义第一次买入任意次买入难度中等简单⏱️ 复杂度分析指标复杂度时间复杂度O(n)空间复杂度O(n)可优化为 O(1) 空间优化通用inthold-prices[0];intcash0;for(inti1;iprices.length;i){intprevCashcash;cashMath.max(cash,holdprices[i]);holdMath.max(hold,prevCash-prices[i]);}returncash;✅ 一句话总结121 限制“只能买一次”122 允许“反复买卖”区别仅在于持有股票的转移方程。