当前位置：首页 > news >正文

LeetCode 每日一题笔记日期：2025.12.17 题目：3573.买卖股票的最佳时机Ⅴ

news 2026/6/7 23:38:00

LeetCode 每日一题笔记

0. 前言

日期：2025.12.17
题目：3573.买卖股票的最佳时机Ⅴ
难度：中等
标签：动态规划

1. 题目理解

问题描述：
给定整数数组prices表示股票每日价格，整数k表示最多可完成的交易次数（一次“做多”或“做空”平仓算一笔交易）。交易规则支持两种操作：

做多：先买入股票，后卖出平仓（利润=卖出价-买入价）；
做空：先卖出股票（卖空），后买回平仓（利润=卖出价-买回价）。
要求在最多完成k笔交易的前提下，返回能获得的最大利润，未进行任何交易时利润为 0。

示例：

示例 1：
输入：prices = [3,2,6,5,0,3], k = 2
输出：7
解释：

第1天做多买入（价格2），第3天卖出平仓（价格5），利润3（完成1笔交易）；
第5天做空卖出（价格0），第6天买回平仓（价格3），利润-3（放弃该操作）；
最优方案：第1天做多买入（2），第3天卖出（6）利润4；第5天做多买入（0），第6天卖出（3）利润3；总利润7（2笔交易）。

示例 2：
输入：prices = [1,2,3,4,5], k = 1
输出：4
解释：做多：第1天买入（1），第5天卖出（5），利润4（1笔交易）。

示例 3：
输入：prices = [7,6,4,3,1], k = 2
输出：0
解释：无论做多/做空均无利润，最优选择不交易。

2. 解题思路

核心观察

状态维度：每日交易状态可拆分为「天数」「已完成交易次数」「持仓状态」三维：
- 持仓状态：0=无持仓（平仓/未操作）、1=做多持仓（买入未卖）、2=做空持仓（卖空未买回）；
交易规则：
- 做多平仓（1→0）或做空平仓（2→0）算完成1笔交易，交易次数+1；
- 开仓（0→1/0→2）不消耗交易次数，仅平仓消耗；
最优子结构：第i天的最大利润仅依赖第i-1天的状态，符合动态规划特征。

算法步骤

初始化DP数组：定义三维数组dp[i][j][s]表示第i天、完成j笔交易、状态s时的最大利润，初始值设为极小值（表示不可达），仅第0天基础状态初始化；
状态转移：
- 无持仓（0）：来自前一天无持仓、前一天做多平仓、前一天做空平仓；
- 做多持仓（1）：来自前一天做多持仓、前一天无持仓开多仓；
- 做空持仓（2）：来自前一天做空持仓、前一天无持仓开空仓；
结果计算：最后一天所有交易次数下，无持仓状态的最大利润（落袋为安，持仓无利润）。

3. 代码实现

publicstaticlongmaximumProfit(int[]prices,intk){intn=prices.length;// 三维DP数组：dp[i][j][s]// i：第i天；j：已完成j笔交易；s：0=无持仓，1=做多持仓，2=做空持仓long[][][]dp=newlong[n][k+1][3];// 初始化所有状态为极小值（不可达），避免溢出用Long.MIN_VALUE/2for(inti=0;i<n;i++){for(intj=0;j<=k;j++){dp[i][j][0]=Long.MIN_VALUE/2;dp[i][j][1]=Long.MIN_VALUE/2;dp[i][j][2]=Long.MIN_VALUE/2;}}// 第0天初始状态dp[0][0][0]=0;// 无交易、无持仓，利润0dp[0][0][1]=-prices[0];// 无交易、做多开仓，利润=-股价dp[0][0][2]=prices[0];// 无交易、做空开仓，利润=+股价// 遍历每一天处理状态转移for(inti=1;i<n;i++){for(intj=0;j<=k;j++){// 状态0：无持仓dp[i][j][0]=Math.max(dp[i][j][0],dp[i-1][j][0]);// 前一天无持仓if(j>=1){// 前一天做多持仓，今日平仓（交易次数+1）dp[i][j][0]=Math.max(dp[i][j][0],dp[i-1][j-1][1]+prices[i]);// 前一天做空持仓，今日平仓（交易次数+1）dp[i][j][0]=Math.max(dp[i][j][0],dp[i-1][j-1][2]-prices[i]);}// 状态1：做多持仓dp[i][j][1]=Math.max(dp[i][j][1],dp[i-1][j][1]);// 前一天做多持仓dp[i][j][1]=Math.max(dp[i][j][1],dp[i-1][j][0]-prices[i]);// 今日开多仓// 状态2：做空持仓dp[i][j][2]=Math.max(dp[i][j][2],dp[i-1][j][2]);// 前一天做空持仓dp[i][j][2]=Math.max(dp[i][j][2],dp[i-1][j][0]+prices[i]);// 今日开空仓}}// 最后一天所有交易次数下，无持仓的最大利润longmaxProfit=0;for(intj=0;j<=k;j++){maxProfit=Math.max(maxProfit,dp[n-1][j][0]);}returnmaxProfit;}

4. 代码优化说明

官方题解优化点

空间优化：将三维DP压缩为二维f[j][s]（仅保留交易次数和状态），利用“逆序遍历交易次数”避免状态覆盖，空间复杂度从 O(nk3) 降至 O(k*3)；
状态合并：简化状态转移逻辑，将每日价格遍历与交易次数逆序遍历结合，减少冗余计算；
边界调整：通过k+2长度的数组规避交易次数边界判断，代码更简洁。

官方题解代码注释

classSolution{publiclongmaximumProfit(int[]prices,intk){// 二维数组：f[j][s] 表示完成j-1笔交易、状态s时的最大利润（空间压缩）long[][]f=newlong[k+2][3];// 初始化不可达状态（防止溢出）for(intj=1;j<=k+1;j++){f[j][1]=Long.MIN_VALUE/2;}f[0][0]=Long.MIN_VALUE/2;// 遍历每日价格，逆序处理交易次数（避免覆盖）for(intp:prices){for(intj=k+1;j>0;j--){// 状态0：无持仓，来自做多平仓/做空平仓/无持仓f[j][0]=Math.max(f[j][0],Math.max(f[j][1]+p,f[j][2]-p));// 状态1：做多持仓，来自前序无持仓开仓f[j][1]=Math.max(f[j][1],f[j-1][0]-p);// 状态2：做空持仓，来自前序无持仓开仓f[j][2]=Math.max(f[j][2],f[j-1][0]+p);}}// 最终取完成k笔交易后无持仓的最大利润returnf[k+1][0];}}