公司网站服务器选择无锡培训网站建设

公司网站服务器选择,无锡培训网站建设,电商怎么自学,石家庄手机网站开发LeetCode 每日一题笔记 0. 前言 日期#xff1a;2025.12.17题目#xff1a;3573.买卖股票的最佳时机Ⅴ难度#xff1a;中等标签#xff1a;动态规划 1. 题目理解 问题描述#xff1a; 给定整数数组 prices 表示股票每日价格#xff0c;整数 k 表示最多可完成的交易次数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总利润72笔交易。示例 2输入prices [1,2,3,4,5], k 1输出4解释做多第1天买入1第5天卖出5利润41笔交易。示例 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){intnprices.length;// 三维DP数组dp[i][j][s]// i第i天j已完成j笔交易s0无持仓1做多持仓2做空持仓long[][][]dpnewlong[n][k1][3];// 初始化所有状态为极小值不可达避免溢出用Long.MIN_VALUE/2for(inti0;in;i){for(intj0;jk;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(inti1;in;i){for(intj0;jk;j){// 状态0无持仓dp[i][j][0]Math.max(dp[i][j][0],dp[i-1][j][0]);// 前一天无持仓if(j1){// 前一天做多持仓今日平仓交易次数1dp[i][j][0]Math.max(dp[i][j][0],dp[i-1][j-1][1]prices[i]);// 前一天做空持仓今日平仓交易次数1dp[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]);// 今日开空仓}}// 最后一天所有交易次数下无持仓的最大利润longmaxProfit0;for(intj0;jk;j){maxProfitMath.max(maxProfit,dp[n-1][j][0]);}returnmaxProfit;}4. 代码优化说明官方题解优化点空间优化将三维DP压缩为二维f[j][s]仅保留交易次数和状态利用“逆序遍历交易次数”避免状态覆盖空间复杂度从 O(nk3) 降至 O(k*3)状态合并简化状态转移逻辑将每日价格遍历与交易次数逆序遍历结合减少冗余计算边界调整通过k2长度的数组规避交易次数边界判断代码更简洁。官方题解代码注释classSolution{publiclongmaximumProfit(int[]prices,intk){// 二维数组f[j][s] 表示完成j-1笔交易、状态s时的最大利润空间压缩long[][]fnewlong[k2][3];// 初始化不可达状态防止溢出for(intj1;jk1;j){f[j][1]Long.MIN_VALUE/2;}f[0][0]Long.MIN_VALUE/2;// 遍历每日价格逆序处理交易次数避免覆盖for(intp:prices){for(intjk1;j0;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[k1][0];}}5. 复杂度分析原代码复杂度时间复杂度O(n*k)。需遍历n天每天遍历k1次交易次数每次处理3种状态均为常数级操作空间复杂度O(n*k)。三维DP数组大小为n*(k1)*3主导空间开销。官方题解复杂度时间复杂度O(n*k)。遍历n天每天逆序遍历k1次交易次数时间效率与原代码一致空间复杂度O(k)。二维数组大小为(k2)*3空间复杂度从线性级降至常数级相对于n。6. 总结题目核心本题是“带做空机制的有限次数股票交易”问题核心是拆分持仓状态动态规划状态转移关键在于明确“平仓算交易次数开仓不算”的规则区分做多/做空两种持仓状态的转移逻辑最终结果仅考虑无持仓状态持仓未平仓无实际利润。关键知识点DP状态压缩利用“当天状态仅依赖前一天”的特性将三维DP压缩为二维大幅降低空间开销状态初始化用极小值标记不可达状态避免溢出需将初始值设为Long.MIN_VALUE/2逆序遍历官方题解中逆序处理交易次数是01背包思想的延伸防止同一交易次数被重复更新。刷题启示复杂状态的DP问题先拆分清晰状态维度如本题的“天数、交易次数、持仓状态”再逐一推导转移逻辑空间优化优先考虑“状态压缩”重点观察状态依赖关系仅依赖前一阶段则可压缩涉及大数运算时需注意溢出问题如用Long存储利润初始值规避MIN_VALUE直接运算。