线性动态规划：买卖股票的最佳时机 IV 题目描述 给定一个整数数组 prices 表示股票每天的价格，以及一个整数 k ，表示你最多可以完成 k 笔交易（买入和卖出合为一笔交易）。你不能同时参与多笔交易（必须在再次购买前出售掉之前的股票）。设计算法计算你能获得的最大利润。 示例 输入：k = 2, prices = [ 3,2,6,5,0,3 ] 输出：7 解释：第2天买入（价格=2），第3天卖出（价格=6），利润=4；第5天买入（价格=0），第6天卖出（价格=3），利润=3；总利润=7。 解题思路 此问题需分情况讨论： 当 k ≥ 数组长度一半时 ：问题退化为无限次交易，可用贪心法解决（所有上涨日都交易）。 当 k 较小 ：使用动态规划，定义状态为天数、交易次数、是否持有股票。 步骤1：定义状态 设 dp[i][j][0] 表示第 i 天结束时，最多完成 j 笔交易，且未持有股票的最大利润。 dp[i][j][1] 表示第 i 天结束时，最多完成 j 笔交易，且持有股票的最大利润。 关键点 ： 买入股票时算开启一笔交易，因此买入时交易次数 j 需减1。 每天可选择买入、卖出或休息。 步骤2：状态转移方程 对于第 i 天（i≥1）： 未持有股票 （ dp[i][j][0] ）： 前一天也未持有： dp[i-1][j][0] 前一天持有，今天卖出： dp[i-1][j][1] + prices[i] 方程： dp[i][j][0] = max(dp[i-1][j][0], dp[i-1][j][1] + prices[i]) 持有股票 （ dp[i][j][1] ）： 前一天已持有： dp[i-1][j][1] 前一天未持有，今天买入（消耗一次交易）： dp[i-1][j-1][0] - prices[i] 方程： dp[i][j][1] = max(dp[i-1][j][1], dp[i-1][j-1][0] - prices[i]) 步骤3：初始化 第0天（i=0）时： 未持有股票： dp[0][j][0] = 0 （未开始交易，利润为0） 持有股票： dp[0][j][1] = -prices[0] （买入股票，利润为负的股价） 交易次数为0（j=0）时： 未持有股票： dp[i][0][0] = 0 持有股票： dp[i][0][1] = -∞ （不允许交易，不可能持有股票） 步骤4：优化与特判 空间优化 ：由于状态只依赖前一天，可压缩为二维数组。 k 过大时的贪心优化 ：若 k ≥ n/2 ，问题等价于无限次交易，直接计算所有正差价之和。 示例推导（k=2, prices=[ 3,2,6,5,0,3]） 贪心优化检查 ：k=2 < n/2=3，需用DP。 初始化 ： dp[0][1][0]=0, dp[0][1][1]=-3 dp[0][2][0]=0, dp[0][2][1]=-3 逐天计算 （简化展示关键值）： 第2天（价格=2）：买入成本更低，更新持有状态。 第3天（价格=6）：卖出利润=4，更新未持有状态。 第5天（价格=0）：买入成本为0，结合之前利润。 第6天（价格=3）：卖出利润=3，总利润=4+3=7。 最终答案： dp[n-1][k][0] （最后一天未持有股票的最大利润）。