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];}}5. 复杂度分析
原代码复杂度
- 时间复杂度：O(n*k)。需遍历
n天，每天遍历k+1次交易次数，每次处理3种状态，均为常数级操作； - 空间复杂度：O(n*k)。三维DP数组大小为
n*(k+1)*3，主导空间开销。
官方题解复杂度
- 时间复杂度：O(n*k)。遍历
n天，每天逆序遍历k+1次交易次数，时间效率与原代码一致； - 空间复杂度：O(k)。二维数组大小为
(k+2)*3，空间复杂度从线性级降至常数级（相对于n）。
6. 总结
题目核心
本题是“带做空机制的有限次数股票交易”问题，核心是拆分持仓状态+动态规划状态转移，关键在于：
- 明确“平仓算交易次数，开仓不算”的规则；
- 区分做多/做空两种持仓状态的转移逻辑；
- 最终结果仅考虑无持仓状态（持仓未平仓无实际利润）。
关键知识点
- DP状态压缩：利用“当天状态仅依赖前一天”的特性，将三维DP压缩为二维，大幅降低空间开销；
- 状态初始化：用极小值标记不可达状态，避免溢出需将初始值设为
Long.MIN_VALUE/2； - 逆序遍历：官方题解中逆序处理交易次数，是01背包思想的延伸，防止同一交易次数被重复更新。
刷题启示
- 复杂状态的DP问题，先拆分清晰状态维度（如本题的“天数、交易次数、持仓状态”），再逐一推导转移逻辑；
- 空间优化优先考虑“状态压缩”，重点观察状态依赖关系（仅依赖前一阶段则可压缩）；
- 涉及大数运算时，需注意溢出问题（如用Long存储利润，初始值规避MIN_VALUE直接运算）。
