Java+Leetcode+动态规划VII

YSRM

797人浏览 · 2025-09-24 16:41:10

YSRM · 2025-09-24 16:41:10 发布

122.买卖股票的最佳时机II

给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。

在每一天，你可以决定是否购买和/或出售股票。你在任何时候最多只能持有一股股票。然而，你可以在 同一天 多次买卖该股票，但要确保你持有的股票不超过一股。

返回 你能获得的最大利润 。

示例 1：
输入：prices = [7,1,5,3,6,4]
输出：7
解释：在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4。
随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3。
最大总利润为 4 + 3 = 7 。
示例 2：
输入：prices = [1,2,3,4,5]
输出：4
解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4。
最大总利润为 4 。
示例 3：
输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 交易无法获得正利润，所以不参与交易可以获得最大利润，最大利润为 0。
提示：

1 <= prices.length <= 3 * 104

0 <= prices[i] <= 104

原理

定义状态：

使用二维数组 dp，其中：

dp[i][0]：第 i 天结束时不持有股票的最大利润。

dp[i][1]：第 i 天结束时持有股票的最大利润。

目标是求 dp[n-1][0]，因为最后一天不持有股票（卖出或不交易）会产生最大利润。

初始化：

第0天：

dp[0][0] = 0：不持有股票，利润为0。

dp[0][1] = -prices[0]：持有股票，利润为负的买入价格。

状态转移：

对于每一天 i（从1到 n-1）：

持有股票（dp[i][1]）：

继续持有：dp[i-1][1]。

前一天不持有，当天买入：dp[i-1][0] - prices[i]。

取最大值：dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i])。

不持有股票（dp[i][0]）：

继续不持有：dp[i-1][0]。

前一天持有，当天卖出：dp[i-1][1] + prices[i]。

取最大值：dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])。

允许同一天买卖，因为状态转移基于前一天状态，买卖操作在同一天内可合并。

优化可能性：

状态只依赖前一天，可以用两个变量（hold 和 notHold）代替 dp 数组，优化空间到 O(1)。

贪心算法更简单：累加所有正价格差（prices[i] - prices[i-1]），但这里使用动态规划。

时间复杂度：

遍历数组：O(n)，n 为 prices.length。

每次操作（比较、加减）：O(1)。

总时间复杂度：O(n)。

空间复杂度：

使用二维数组 dp[n][2]：O(n)。

代码

class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        // 创建二维dp数组，dp[i][0]表示第i天不持有股票的最大利润，dp[i][1]表示持有股票的最大利润
        int[][] dp = new int[n][2];
        
        // 初始化第0天状态
        dp[0][0] = 0;           // 第0天不持有股票，利润为0
        dp[0][1] = -prices[0];  // 第0天持有股票，利润为负的买入价格
        
        // 遍历从第1天到最后一天
        for (int i = 1; i < n; ++i) {
            // 持有股票的最大利润：
            // 1. 前一天已持有（dp[i-1][1]）
            // 2. 前一天不持有，当天买入（dp[i-1][0] - prices[i]）
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
            
            // 不持有股票的最大利润：
            // 1. 前一天不持有（dp[i-1][0]）
            // 2. 前一天持有，当天卖出（dp[i-1][1] + prices[i]）
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
        }
        
        // 返回最后一天不持有股票的最大利润
        return dp[n - 1][0];
    }
}

123.买卖股票的最佳时机III

给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成两笔交易。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1:

输入：prices = [3,3,5,0,0,3,1,4]
输出：6
解释：在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。
     随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。

示例 2：

输入：prices = [1,2,3,4,5]
输出：4
解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。   
     注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。   
     因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。

示例 3：

输入：prices = [7,6,4,3,1] 
输出：0 
解释：在这个情况下, 没有交易完成, 所以最大利润为 0。

示例 4：

输入：prices = [1]
输出：0

提示：

1 <= prices.length <= 105
0 <= prices[i] <= 105

原理

定义状态：

使用二维数组 dp[i][j]，表示第 i 天处于状态 j 的最大利润：

j = 0：无操作（默认0，未使用）。

j = 1：第一次持有股票。

j = 2：第一次卖出股票。

j = 3：第二次持有股票。

j = 4：第二次卖出股票。

目标是 dp[n-1][4]，表示最后一天完成最多两次交易的最大利润。

初始化：

第0天：

dp[0][1] = -prices[0]：第一次买入，利润为负价格。

dp[0][3] = -prices[0]：第二次买入（理论上不可达，但初始化为负价格）。

dp[0][0] = 0, dp[0][2] = 0, dp[0][4] = 0（默认）。

如果 n = 1，无法交易，返回0。

状态转移：

对于每一天 i（从1到 n-1）：

第一次持有（dp[i][1]）：

继续持有：dp[i-1][1]。

当天买入：-prices[i]（假设从无操作状态开始）。

取最大值：dp[i][1] = max(dp[i-1][1], -prices[i])。

第一次卖出（dp[i][2]）：

继续不持有：dp[i-1][2]。

当天卖出：dp[i-1][1] + prices[i]。

取最大值：dp[i][2] = max(dp[i-1][2], dp[i-1][1] + prices[i])。

第二次持有（dp[i][3]）：

继续持有：dp[i-1][3]。

第一次卖出后当天买入：dp[i-1][2] - prices[i]。

取最大值：dp[i][3] = max(dp[i-1][3], dp[i-1][2] - prices[i])。

第二次卖出（dp[i][4]）：

继续不持有：dp[i-1][4]。

当天卖出：dp[i-1][3] + prices[i]。

取最大值：dp[i][4] = max(dp[i-1][4], dp[i-1][3] + prices[i])。

状态 j=0 未使用，始终为0。

优化可能性：

可以用一维数组（5个变量）代替 dp 数组，优化空间到 O(1)，因为状态只依赖前一天。

当前代码使用二维数组，逻辑更直观。

时间复杂度：

遍历数组：O(n)，n 为 prices.length。

每次更新5个状态：O(1)。

总时间复杂度：O(n)。

空间复杂度：

使用二维数组 dp[n][5]：O(n)。

代码

import java.util.*;

class Solution {
    public int maxProfit(int[] prices) {
        // 特殊情况：如果只有一天，无法交易，返回0
        if (prices.length == 1) return 0;
        
        // 创建二维dp数组，dp[i][j]表示第i天处于状态j的最大利润
        // 状态j：0（无操作），1（第一次持有），2（第一次卖出），3（第二次持有），4（第二次卖出）
        int[][] dp = new int[prices.length][5];
        
        // 初始化第0天状态
        dp[0][1] = -prices[0]; // 第一次买入
        dp[0][3] = -prices[0]; // 第二次买入（假设先买入，但实际不可达，仅初始化）
        // dp[0][0], dp[0][2], dp[0][4] 默认0（无操作、卖出状态）
        
        // 遍历从第1天到最后一天
        for (int i = 1; i < prices.length; i++) {
            // 第一次持有：继续持有或当天买入
            dp[i][1] = Math.max(dp[i-1][1], -prices[i]);
            // 第一次卖出：继续不持有或当天卖出
            dp[i][2] = Math.max(dp[i-1][2], dp[i-1][1] + prices[i]);
            // 第二次持有：继续持有或在第一次卖出后当天买入
            dp[i][3] = Math.max(dp[i-1][3], dp[i-1][2] - prices[i]);
            // 第二次卖出：继续不持有或当天卖出
            dp[i][4] = Math.max(dp[i-1][4], dp[i-1][3] + prices[i]);
            
            // 调试输出：打印当前天的状态
            System.out.print(dp[i][1] + " " + dp[i][2] + " " + dp[i][3] + " " + dp[i][4] + "\n");
        }
        
        // 返回最后一天第二次卖出的最大利润
        return dp[prices.length - 1][4];
    }
}

188.买卖股票的最佳时机IV

给你一个整数数组 prices 和一个整数 k ，其中 prices[i] 是某支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说，你最多可以买 k 次，卖 k 次。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1：
输入：k = 2, prices = [2,4,1]
输出：2
解释：在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。
示例 2：
输入：k = 2, prices = [3,2,6,5,0,3]
输出：7
解释：在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。
     随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。
提示：

1 <= k <= 100

1 <= prices.length <= 1000

0 <= prices[i] <= 1000

原理

定义状态：

使用二维数组 dp[i][j]，表示第 i 天处于状态 j 的最大利润：

j = 0：无操作。

j = 1：第一次持有股票。

j = 2：第一次卖出股票。

j = 3：第二次持有股票。

j = 4：第二次卖出股票。

...

j = 2*k-1：第 k 次持有股票。

j = 2*k：第 k 次卖出股票。

目标是 dp[n-1][2*k]，表示最后一天完成最多 k 次交易的最大利润。

初始化：

第0天：

奇数状态（j = 1, 3, 5, ...）：第1, 2, 3...次买入，dp[0][2*i+1] = -prices[0]。

偶数状态（j = 0, 2, 4, ...）：无操作或第1, 2...次卖出，默认0。

如果 n = 1，无法交易，返回0。

状态转移：

对于每一天 i（从1到 n-1）：

第 j 次持有（dp[i][2*j-1]）：

继续持有：dp[i-1][2*j-1]。

前一天为第 j-1 次卖出（或无操作，j=1 时），当天买入：dp[i-1][2*j-2] - prices[i]。

取最大值：dp[i][2*j-1] = max(dp[i-1][2*j-1], dp[i-1][2*j-2] - prices[i])。

第 j 次卖出（dp[i][2*j]）：

继续不持有：dp[i-1][2*j]。

前一天为第 j 次持有，当天卖出：dp[i-1][2*j-1] + prices[i]。

取最大值：dp[i][2*j] = max(dp[i-1][2*j], dp[i-1][2*j-1] + prices[i])。

优化可能性：

当 k 较大（例如 k >= n/2），问题等价于“买卖股票 II”（无限次交易），可用贪心算法。

空间可优化到 O(1)，用一维数组 dp[2*k+1] 替代 dp[n][2*k+1]，因为状态只依赖前一天。

时间复杂度：

遍历天数：O(n)，n 为 prices.length。

遍历状态：O(k)。

总时间复杂度：O(n * k)。

空间复杂度：

使用二维数组 dp[n][2*k+1]：O(n * k)。

代码

class Solution {
    public int maxProfit(int k, int[] prices) {
        // 特殊情况：如果只有一天，无法交易，返回0
        if (prices.length == 1) return 0;
        
        // 创建二维dp数组，dp[i][j]表示第i天处于状态j的最大利润
        // 状态j：0（无操作），1（第一次持有），2（第一次卖出），3（第二次持有），4（第二次卖出）... 2*k（第k次卖出）
        int[][] dp = new int[prices.length][2 * k + 1];
        
        // 初始化第0天状态
        // 奇数状态（1,3,5...）表示第1,2,3...次持有股票，初始化为负的买入价格
        for (int i = 0; i < k; i++) {
            dp[0][2 * i + 1] = -prices[0];
        }
        // 偶数状态（0,2,4...）表示无操作或第1,2...次卖出，默认0
        
        // 遍历从第1天到最后一天
        for (int i = 1; i < prices.length; i++) {
            // 遍历k次交易的每个状态
            for (int j = 1; j <= k; j++) {
                // 第j次持有股票（状态2*j-1）：
                // 1. 继续持有：dp[i-1][2*j-1]
                // 2. 前一天为第j-1次卖出（或无操作，j=1时），当天买入：dp[i-1][2*j-2] - prices[i]
                dp[i][2 * j - 1] = Math.max(dp[i - 1][2 * j - 1], dp[i - 1][2 * j - 2] - prices[i]);
                
                // 第j次卖出股票（状态2*j）：
                // 1. 继续不持有：dp[i-1][2*j]
                // 2. 前一天为第j次持有，当天卖出：dp[i-1][2*j-1] + prices[i]
                dp[i][2 * j] = Math.max(dp[i - 1][2 * j], dp[i - 1][2 * j - 1] + prices[i]);
            }
        }
        
        // 返回最后一天第k次卖出的最大利润
        return dp[prices.length - 1][2 * k];
    }
}

309.买卖股票的最佳时机含冷冻期

给定一个整数数组prices，其中第 prices[i] 表示第 i 天的股票价格。

设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:

卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1:
输入: prices = [1,2,3,0,2]
输出: 3 
解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]
示例 2:
输入: prices = [1]
输出: 0
提示：

1 <= prices.length <= 5000

0 <= prices[i] <= 1000

原理

定义状态：

使用二维数组 dp[i][j]，表示第 i 天处于状态 j 的最大利润：

j = 0：持有股票。

j = 1：不持有股票且不在冷冻期（可买入）。

j = 2：当天卖出股票。

j = 3：处于冷冻期（不可买入）。

目标是最后一天不持有股票的最大利润：max(dp[n-1][1], dp[n-1][2], dp[n-1][3])。

初始化：

第0天：

dp[0][0] = -prices[0]：持有股票（买入）。

dp[0][1] = 0：不持有且不在冷冻期。

dp[0][2] = 0：卖出（不可达，默认0）。

dp[0][3] = 0：冷冻期（不可达，默认0）。

状态转移：

对于每一天 i（从1到 n-1）：

持有股票（dp[i][0]）：

继续持有：dp[i-1][0]。

前一天可买入，当天买入：dp[i-1][1] - prices[i]。

前一天冷冻期结束，当天买入：dp[i-1][3] - prices[i]。

取最大值：dp[i][0] = max(dp[i-1][0], dp[i-1][1] - prices[i], dp[i-1][3] - prices[i])。

不持有且不在冷冻期（dp[i][1]）：

继续不持有：dp[i-1][1]。

前一天冷冻期结束：dp[i-1][3]。

取最大值：dp[i][1] = max(dp[i-1][1], dp[i-1][3])。

当天卖出（dp[i][2]）：

前一天持有，当天卖出：dp[i-1][0] + prices[i]。

dp[i][2] = dp[i-1][0] + prices[i]。

冷冻期（dp[i][3]）：

前一天卖出，进入冷冻期：dp[i-1][2]。

dp[i][3] = dp[i-1][2]。

空间优化：

使用滚动数组 dp[2][4]，通过 i % 2 交替存储当前和前一天状态，空间从 O(n) 优化到 O(1)。

状态转移只依赖前一天的 dp[i-1][j]。

时间复杂度：

遍历天数：O(n)，n 为 prices.length。

每次更新4个状态：O(1)。

总时间复杂度：O(n)。

空间复杂度：

使用滚动数组 dp[2][4]：O(1)。

代码

class Solution {
    /**
     * 状态定义：
     * dp[i][0]: 第i天持有股票的最大利润
     * dp[i][1]: 第i天不持有股票且不在冷冻期（可买入）的最大利润
     * dp[i][2]: 第i天卖出股票的最大利润
     * dp[i][3]: 第i天处于冷冻期的最大利润
     */
    public int maxProfit(int[] prices) {
        int len = prices.length;
        // 使用滚动数组优化空间，dp[2][4]交替存储当前和前一天的状态
        int[][] dp = new int[2][4];
        
        // 初始化第0天状态
        dp[0][0] = -prices[0]; // 持有股票（买入）
        // dp[0][1] = 0;        // 不持有且不在冷冻期，默认0
        // dp[0][2] = 0;        // 卖出，默认0（不可达）
        // dp[0][3] = 0;        // 冷冻期，默认0（不可达）
        
        // 遍历从第1天到最后一天
        for (int i = 1; i < len; i++) {
            // 持有股票：
            // 1. 前一天持有：dp[i-1][0]
            // 2. 前一天不持有且可买入，当天买入：dp[i-1][1] - prices[i]
            // 3. 前一天冷冻期结束，当天买入：dp[i-1][3] - prices[i]
            dp[i % 2][0] = Math.max(Math.max(dp[(i - 1) % 2][0], dp[(i - 1) % 2][1] - prices[i]), 
                                    dp[(i - 1) % 2][3] - prices[i]);
            
            // 不持有且不在冷冻期：
            // 1. 前一天不持有且可买入：dp[i-1][1]
            // 2. 前一天冷冻期结束：dp[i-1][3]
            dp[i % 2][1] = Math.max(dp[(i - 1) % 2][1], dp[(i - 1) % 2][3]);
            
            // 当天卖出：
            // 前一天持有，当天卖出：dp[i-1][0] + prices[i]
            dp[i % 2][2] = dp[(i - 1) % 2][0] + prices[i];
            
            // 冷冻期：
            // 前一天卖出，进入冷冻期：dp[i-1][2]
            dp[i % 2][3] = dp[(i - 1) % 2][2];
        }
        
        // 返回最后一天不持有股票的最大利润（可买入、卖出或冷冻期）
        return Math.max(Math.max(dp[(len - 1) % 2][1], dp[(len - 1) % 2][2]), dp[(len - 1) % 2][3]);
    }
}

AI Agent技术社区

Agent 垂直技术社区，欢迎活跃、内容共建。

更多推荐

SeedVR2终极指南：如何用单步扩散模型实现专业级视频修复

还在为老旧视频的模糊画质而烦恼吗？面对抖动严重的监控录像或褪色的家庭影像，你是否曾希望有一种简单高效的修复方案？SeedVR2正是为解决这些痛点而生的一站式视频修复工具。作为字节跳动推出的先进视频修复模型，它能够在单步推理中实现专业级的视频质量提升，彻底改变了传统视频修复的工作流程。## 核心价值：为什么选择SeedVR2进行视频修复？**传统视频修复的三大瓶颈**：1. **计算成本高

AI Agent技术社区

深度解析Amlogic S9xxx电视盒子Armbian系统：从闲置设备到Linux服务器的终极实战指南

你是否拥有一台闲置的Amlogic S9xxx系列电视盒子？想让它摆脱单一的视频播放功能，变身为功能强大的Linux服务器、开发平台或家庭媒体中心？本指南将为你详细解析如何通过Armbian系统实现这一转变，让你的电视盒子重获新生，成为高性能的Linux设备。Armbian系统基于Debian/Ubuntu构建，专为ARM芯片优化，提供了完整的Linux生态支持。## 🎯 核心价值与独特优势

AI Agent技术社区

CANN/runtime Event管理API

本章节描述 CANN Runtime 的 Event 管理接口，用于事件的创建、记录、同步、计时及 IPC 跨进程共享。- [`aclError aclrtCreateEvent(aclrtEvent *event)`](#aclrtCreateEvent)：创建Event，创建出来的Event可用于统计两个Event之间的耗时、多Stream之间的任务同步等场景。- [`aclError