dp算法 力扣309最佳买卖股票时机含冷冻期

简介: dp算法 力扣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问题,先需要确定dp[i]表示的含义:dp[i]表示第i天的最大利润。

当处于第i天时,有三种状态:

  1. 无股票,但不处于冷冻期
  2. 无股票,但处于冷冻期
  3. 有股票

故我们需要设置dp表为dp[n][3]。

对于这三种状态,我们可以得知的状态转化为:

即,状态转移方程为:


(有股票)dp[i][0] = Math.max(dp[i-1][0],dp[i-1][2]-prices[i]);

(无股票,但处于冷冻期)dp[i][1] = dp[i-1][0]+prices[i];

( 无股票,但不处于冷冻期)dp[i][2] = Math.max(dp[i-1][2],dp[i-1][1]);


初始化过程: 对于第一天,可以选择购买股票进入有股票状态,也可以选择不购买股票,进入无股票,但不处于冷冻期状态。

最终的返回值是取这三种状态下的最大值。

三、代码

class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        int[][] dp = new int[n][3];
        dp[0][0] = prices[0]*(-1);
        for(int i=1;i<n;i++){
            dp[i][0] = Math.max(dp[i-1][0],dp[i-1][2]-prices[i]);
            dp[i][1] = dp[i-1][0]+prices[i];
            dp[i][2] = Math.max(dp[i-1][2],dp[i-1][1]);
        }
        return Math.max(Math.max(dp[n-1][1],dp[n-1][2]),dp[n-1][0]);
    }
}

提交截图:



结语

这篇博客如果对你有帮助,给博主一个免费的点赞以示鼓励,欢迎各位🔎点赞👍评论收藏⭐,谢谢!!!

相关文章
|
算法 Python
【Leetcode刷题Python】309. 最佳买卖股票时机含冷冻期
解决LeetCode上309题“最佳买卖股票时机含冷冻期”的Python代码示例,利用动态规划方法计算在含有冷冻期约束下的最大利润。
256 1
|
Go
【LeetCode 热题100】DP 实战进阶:最长递增子序列、乘积最大子数组、分割等和子集(力扣300 / 152/ 416 )(Go语言版)
本文深入解析三道经典的动态规划问题:**最长递增子序列(LIS)**、**乘积最大子数组** 和 **分割等和子集**。 - **300. LIS** 通过 `dp[i]` 表示以第 `i` 个元素结尾的最长递增子序列长度,支持 O(n²) 动态规划与 O(n log n) 的二分优化。 - **152. 乘积最大子数组** 利用正负数特性,同时维护最大值与最小值的状态转移方程。 - **416. 分割等和子集** 转化为 0-1 背包问题,通过布尔型 DP 实现子集和判断。 总结对比了三题的状态定义与解法技巧,并延伸至相关变种问题,助你掌握动态规划的核心思想与灵活应用!
710 1
|
存储 算法
动态规划算法学习一:DP的重要知识点、矩阵连乘算法
这篇文章是关于动态规划算法中矩阵连乘问题的详解,包括问题描述、最优子结构、重叠子问题、递归方法、备忘录方法和动态规划算法设计的步骤。
1839 1
|
算法 Python
【Leetcode刷题Python】121. 买卖股票的最佳时机
解决LeetCode上121题“买卖股票的最佳时机”的Python代码示例,采用一次遍历的方式寻找最佳买卖时机以获得最大利润。
434 1
|
算法 C++
【算法】DP背包问题(C/C++)
【算法】DP背包问题(C/C++)
|
人工智能 算法 BI
【算法】 线性DP(C/C++)
【算法】 线性DP(C/C++)
|
算法
leetcode188 买卖股票的最佳时机IV
leetcode188 买卖股票的最佳时机IV
312 0
|
算法 Python
【Leetcode刷题Python】714. 买卖股票的最佳时机含手续费
提供了两种解决买卖股票最佳时机含手续费问题的Python实现方法:贪心算法和动态规划算法。
322 0
|
机器学习/深度学习 算法 机器人
【水下图像增强融合算法】基于融合的水下图像与视频增强研究(Matlab代码实现)
【水下图像增强融合算法】基于融合的水下图像与视频增强研究(Matlab代码实现)
1076 0
|
数据采集 分布式计算 并行计算
mRMR算法实现特征选择-MATLAB
mRMR算法实现特征选择-MATLAB
631 2

热门文章

最新文章