算法修炼Day51|● 309.最佳买卖股票时机含冷冻期 ● 714.买卖股票的最佳时机含手续费

简介: 算法修炼Day51|● 309.最佳买卖股票时机含冷冻期 ● 714.买卖股票的最佳时机含手续费

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

309. 买卖股票的最佳时机含冷冻期 - 力扣(LeetCode)


1.思路

初始化dp[i][j]数组,表示第i天的最大利润为dp[i][j].

精确的定义状态是个难点,可以定义四种状态:持有股票(当天买入、前一天持有、前一天为保持卖出的状态)、卖出状态(前一天为冷冻期、前一天为卖出状态)、卖出股票(前一天持有股票当天卖出+prices[i])、冷冻期(前一天卖出的状态)


2.代码实现

 1class Solution {
 2    public int maxProfit(int[] prices) {
 3
 4
 5        int len = prices.length;
 6
 7        int[][] dp = new int[len][4];
 8        // 四种状态
 9        // dp[i][0] 持有股票;dp[i][1] 保持卖出股票;dp[i][2]卖出股票;dp[i][3]冷冻期
10
11
12        // 初始化dp数组
13        dp[0][0] = -prices[0];
14        dp[0][1] = 0;
15        dp[0][2] = 0;
16        dp[0][3] = 0;
17
18        for (int i = 1; i < len; i++) {
19            // 持有股票:①前一天持有 ②当天买入 ③冷冻期下一天买入
20            dp[i][0] = Math.max(dp[i - 1][0], Math.max(dp[i - 1][3] - prices[i], dp[i - 1][1] - prices[i]));
21            // 保持卖出股票:①冷冻期②前一天就是保持卖出状态
22            dp[i][1] = Math.max(dp[i - 1][3], dp[i - 1][1]);
23            // 卖出股票操作
24            dp[i][2] = dp[i - 1][0] + prices[i];
25            // 冷冻期
26            dp[i][3] = dp[i - 1][2];
27        }
28
29        return Math.max(dp[len - 1][1], Math.max(dp[len - 1][2], dp[len - 1][3]));
30    }
31}
32

3.复杂度分析

时间复杂度:O(n).

空间复杂度:O(n).


LeetCode:714.买卖股票的最佳时机含手续费

714. 买卖股票的最佳时机含手续费 - 力扣(LeetCode)


1.思路

初始化dp[][][]数组,确定两种状态:持有股票和不持有股票,进行状态转移推演即可。


2.代码实现


 1class Solution {
 2    public int maxProfit(int[] prices, int fee) {
 3        int len = prices.length;
 4
 5        // dp[i][j]
 6
 7        int[][] dp = new int[len][2];
 8        dp[0][0] = -prices[0];
 9        // dp[0][1] = 0; 
10        for (int i = 1; i < len; i++) {
11            // 持有状态:①当天买入;②前一天持有
12            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
13            // 不持有状态:①前一天就是卖出状态;②当天卖出
14            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i] - fee);
15        }
16
17        return dp[len - 1][1];
18    }
19}
20

3.复杂度分析

时间复杂度:O(n).

空间复杂度:O(n).

相关文章
【经典LeetCode算法题目专栏分类】【第10期】排序问题、股票问题与TOP K问题:翻转对、买卖股票最佳时机、数组中第K个最大/最小元素
【经典LeetCode算法题目专栏分类】【第10期】排序问题、股票问题与TOP K问题:翻转对、买卖股票最佳时机、数组中第K个最大/最小元素
|
数据采集 监控 算法
应用动态规划算法解决可转债软件中的最优买卖时机问题
使用动态规划算法解决可转债市场的最佳买卖时机问题。定义状态dp[i][0](持有可转债的最大利润)和dp[i][1](不持有可转债的最大利润),通过状态转移方程更新状态,以max函数求解。提供的Python代码示例展示了如何计算最大利润。将此算法集成到软件中,结合网络爬虫获取实时价格,自动计算并提供买卖建议,助力投资者做出更明智的决策。
198 0
|
算法 数据可视化 数据挖掘
数据分享|R语言改进的K-MEANS(K-均值)聚类算法分析股票盈利能力和可视化
数据分享|R语言改进的K-MEANS(K-均值)聚类算法分析股票盈利能力和可视化
|
机器学习/深度学习 自然语言处理 算法
【视频】K近邻KNN算法原理与R语言结合新冠疫情对股票价格预测|数据分享(下)
【视频】K近邻KNN算法原理与R语言结合新冠疫情对股票价格预测|数据分享
|
机器学习/深度学习 算法 大数据
【视频】K近邻KNN算法原理与R语言结合新冠疫情对股票价格预测|数据分享(上)
【视频】K近邻KNN算法原理与R语言结合新冠疫情对股票价格预测|数据分享
|
算法 Java 索引
[Java·算法·中等] LeetCode122. 买股票的最佳时机 II 解读
[Java·算法·中等] LeetCode122. 买股票的最佳时机 II 解读
91 0
|
存储 算法 JavaScript
JS算法-买卖股票的时机
JS算法-买卖股票的时机
|
5天前
|
传感器 机器学习/深度学习 算法
【使用 DSP 滤波器加速速度和位移】使用信号处理算法过滤加速度数据并将其转换为速度和位移研究(Matlab代码实现)
【使用 DSP 滤波器加速速度和位移】使用信号处理算法过滤加速度数据并将其转换为速度和位移研究(Matlab代码实现)
|
6天前
|
传感器 算法 数据挖掘
基于协方差交叉(CI)的多传感器融合算法matlab仿真,对比单传感器和SCC融合
基于协方差交叉(CI)的多传感器融合算法,通过MATLAB仿真对比单传感器、SCC与CI融合在位置/速度估计误差(RMSE)及等概率椭圆上的性能。采用MATLAB2022A实现,结果表明CI融合在未知相关性下仍具鲁棒性,有效降低估计误差。
|
7天前
|
负载均衡 算法 调度
基于遗传算法的新的异构分布式系统任务调度算法研究(Matlab代码实现)
基于遗传算法的新的异构分布式系统任务调度算法研究(Matlab代码实现)
76 11

热门文章

最新文章