【LetMeFly】3573.买卖股票的最佳时机 V：深度优先搜索 / 动态规划：通俗讲解
力扣题目链接：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-v/
给你一个整数数组prices，其中prices[i]是第i天股票的价格（美元），以及一个整数k。
你最多可以进行k笔交易，每笔交易可以是以下任一类型：
普通交易：在第
i天买入，然后在之后的第j天卖出，其中i < j。你的利润是prices[j] - prices[i]。做空交易：在第
i天卖出，然后在之后的第j天买回，其中i < j。你的利润是prices[i] - prices[j]。
注意：你必须在开始下一笔交易之前完成当前交易。此外，你不能在已经进行买入或卖出操作的同一天再次进行买入或卖出操作。
通过进行最多k笔交易，返回你可以获得的最大总利润。
示例 1:
输入:prices = [1,7,9,8,2], k = 2
输出:14
解释:
我们可以通过 2 笔交易获得 14 美元的利润：- 一笔普通交易：第 0 天以 1 美元买入，第 2 天以 9 美元卖出。
- 一笔做空交易：第 3 天以 8 美元卖出，第 4 天以 2 美元买回。
示例 2:
输入:prices = [12,16,19,19,8,1,19,13,9], k = 3
输出:36
解释:
我们可以通过 3 笔交易获得 36 美元的利润：- 一笔普通交易：第 0 天以 12 美元买入，第 2 天以 19 美元卖出。
- 一笔做空交易：第 3 天以 19 美元卖出，第 4 天以 8 美元买回。
- 一笔普通交易：第 5 天以 1 美元买入，第 6 天以 19 美元卖出。
提示:
2 <= prices.length <= 1031 <= prices[i] <= 1091 <= k <= prices.length / 2
自我评价：好文x1(bushi)
解题方法一：深度优先搜索
定义dfs(i, j, status)含义为：
- 0到i ii天，共进行了j jj次买入或做空操作
- status：0代表第i ii天要到没持有股票状态；1代表第i ii天要到手持股票的状态；2代表第i ii天要到做空的状态
假设买入或做空时立刻消耗交易次数(卖出或还上时交易完成不二次消耗次数)，那么有：
- 如果status为0（这天结束后两清）：可昨天本就两清今天什么都没干(
dfs(i-1, j, 0))，可昨天是手持股票状态今天卖了(dfs(i-1, j, 1) + prices[i])，可昨天是空头状态今天买回来补上了(dfs(i-1, j, 2) - prices[i])。 - 如果status为1（这天结束后手持股票）：可昨天本就持有股票今天什么都没干(
dfs(i-1, j, 1))，可昨天两清今天刚买入(dfs(i-1, j-1, 0) - prices[i])。 - 如果status为2（这天结束后欠还股票）：可昨天就是欠股票状态今天什么都没干(
dfs(i-1, j, 2))，可昨天两清今天做空提前卖了股票(dfs(i-1, j-1, 0) + prices[i])。
边界条件：
- 可用操作次数始终不能为负，如果为负返回“负无穷”
- 天数为-1时（交易开始前）只能处于两清状态，如果交易开始前（i = − 1 i=-1i=−1）状态已经处在持股或空头则说明状态不合法，返回“负无穷”。
时空复杂度：
- 时间复杂度O ( l e n ( p r i c e s ) × k ) O(len(prices)\times k)O(len(prices)×k)
- 空间复杂度O ( l e n ( p r i c e s ) × k ) O(len(prices)\times k)O(len(prices)×k)
AC代码
C++
/* * @LastEditTime: 2025-12-17 23:09:09 */typedeflonglongll;classSolution{private:vector<int>prices;unordered_map<int,ll>cache;inlineintgetKey(inti,intj,intstatus){returni*3000+j*3+status;}lldfs(inti,intj,intstatus){// 0~i天 最多交易j次// status: 0无1买2空头intkey=getKey(i,j,status);if(cache.count(key)){returncache[key];}if(j<0){return-1'000'000'000'000'000;}if(i<0){returnstatus?-1'000'000'000'000'000:0;}if(status==0){returncache[key]=max({dfs(i-1,j,0),dfs(i-1,j,1)+prices[i],dfs(i-1,j,2)-prices[i]});}elseif(status==1){returncache[key]=max(dfs(i-1,j-1,0)-prices[i],dfs(i-1,j,1));}else{returncache[key]=max(dfs(i-1,j-1,0)+prices[i],dfs(i-1,j,2));}}public:llmaximumProfit(vector<int>&prices,intk){this->prices=move(prices);returndfs(this->prices.size()-1,k,0);}};Python
python记得最终返回结果前强制清空下缓存，虽然python也有gc机制但可能gc不及时导致MLE。
''' LastEditTime: 2025-12-17 23:18:54 '''fromtypingimportListfromfunctoolsimportcachefrommathimportinfclassSolution:defmaximumProfit(self,prices:List[int],k:int)->int:n=len(prices)@cachedefdfs(i:int,j:int,status:int)->int:"""0无1有2空头"""ifj<0:return-infifi<0:return-infifstatuselse0ifstatus==0:returnmax(dfs(i-1,j,0),dfs(i-1,j,1)+prices[i],dfs(i-1,j,2)-prices[i])elifstatus==1:returnmax(dfs(i-1,j,1),dfs(i-1,j-1,0)-prices[i])else:returnmax(dfs(i-1,j,2),dfs(i-1,j-1,0)+prices[i])ans=dfs(n-1,k,0)dfs.cache_clear()returnans解题方法二：动态规划
将深度优先搜索翻译成递推：
ifstatus==0:returnmax(dfs(i-1,j,0),dfs(i-1,j,1)+prices[i],dfs(i-1,j,2)-prices[i])elifstatus==1:returnmax(dfs(i-1,j,1),dfs(i-1,j-1,0)-prices[i])else:returnmax(dfs(i-1,j,2),dfs(i-1,j-1,0)+prices[i])翻译为：
dp[i][j][0]=max(dp[i-1][j][0],dp[i-1][j][1]+price,dp[i-1][j][2]-price)dp[i][j][1]=max(dp[i-1][j][1],dp[i-1][j-1][0]-price)dp[i][j][2]=max(dp[i-1][j][2],dp[i-1][j-1][0]+price)注意为了防止下标出现-1可以令所有i在作dp下标时加上1：
dp[i+1][j][0]=max(dp[i][j][0],dp[i][j][1]+price,dp[i][j][2]-price)dp[i+1][j][1]=max(dp[i][j][1],dp[i][j-1][0]-price)dp[i+1][j][2]=max(dp[i][j][2],dp[i][j-1][0]+price)时空复杂度：
- 时间复杂度O ( l e n ( p r i c e s ) × k ) O(len(prices)\times k)O(len(prices)×k)
- 空间复杂度O ( l e n ( p r i c e s ) × k ) O(len(prices)\times k)O(len(prices)×k)
AC代码
Python
''' LastEditTime: 2025-12-17 23:51:56 '''fromtypingimportListfrommathimportinfclassSolution:defmaximumProfit(self,prices:List[int],k:int)->int:n=len(prices)# dp[i][j][status]: i有效范围0~n-1，j有效范围0~k，这俩都多开一个无效状态的空间dp=[[[-inf]*3for_inrange(k+2)]for_inrange(n+1)]forjinrange(1,k+2):dp[0][j][0]=0fori,priceinenumerate(prices):forjinrange(1,k+2):dp[i+1][j][0]=max(dp[i][j][0],dp[i][j][1]+price,dp[i][j][2]-price)dp[i+1][j][1]=max(dp[i][j][1],dp[i][j-1][0]-price)dp[i+1][j][2]=max(dp[i][j][2],dp[i][j-1][0]+price)returndp[-1][-1][0]解题方法三：动态规划+空间优化
不难发现第i ii天（dp[i+1][xx][x]）数据仅和第i − 1 i-1i−1天有关（dp[i][xx][x]），因此可以优化掉数组第一维。
注意j要倒序遍历，因为j依赖的是上一天的j-1，如果先更新j-1再更新j则会重复计算。
时空复杂度：
- 时间复杂度O ( l e n ( p r i c e s ) × k ) O(len(prices)\times k)O(len(prices)×k)
- 空间复杂度O ( k ) O(k)O(k)
AC代码
Python
''' LastEditTime: 2025-12-17 23:58:31 '''fromtypingimportListfrommathimportinfclassSolution:defmaximumProfit(self,prices:List[int],k:int)->int:n=len(prices)# dp[i][j][status]: i有效范围0~n-1，j有效范围0~k，这俩都多开一个无效状态的空间dp=[[-inf]*3for_inrange(k+2)]forjinrange(1,k+2):dp[j][0]=0fori,priceinenumerate(prices):forjinrange(k+1,0,-1):dp[j][0]=max(dp[j][0],dp[j][1]+price,dp[j][2]-price)dp[j][1]=max(dp[j][1],dp[j-1][0]-price)dp[j][2]=max(dp[j][2],dp[j-1][0]+price)returndp[-1][0]同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~
千篇源码题解已开源
