赞
踩
题目 | 关键点 |
---|---|
121. 买卖股票的最佳时机 - 力扣(LeetCode) | dp数组为持有和不持有两种情况的最大金额,每种情况又分为现在和之前。所以一共分析四种状态。 |
122. 买卖股票的最佳时机 II - 力扣(LeetCode) | 变化是在推导今天持有时,要记得加上之前不持有的利润 |
123. 买卖股票的最佳时机 III - 力扣(LeetCode) | 分四个状态去讨论 |
188. 买卖股票的最佳时机 IV - 力扣(LeetCode) | 找四个状态的规律,推广到k个。 |
309. 最佳买卖股票时机含冷冻期 - 力扣(LeetCode) | 记忆状态流转图。 |
714. 买卖股票的最佳时机含手续费 - 力扣(LeetCode) | 卖出要手续费,减去手续费就行了 |
给定一个数组 prices ,它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票,并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润,返回 0 。
使用五步法分析:
确定dp数组以及下标含义:dp[i][0]
表示第i天持有股票所得最多现金。dp[i][1]
表示第i天不持有股票所得最多现金。
以上两种情况,每一种情况都有两个状态推导。
dp[i][0]
可以由两个状态推导而来:
dp[i - 1][0]
。-price[i]
。dp[i][1]
也可以由两个状态推导而来:
dp[i - 1][1]
。dp[i - 1][0] + prices[i]
。dp数组初始化:dp[0][0]
为第0天持有股票,dp[0][0] -= prices[i]
。dp[0][1]
表示第0天不持有股票,dp[0][1] = 0
。
遍历顺序:从前往后。
举例推导dp。
class Solution { public int maxProfit(int[] prices) { int n = prices.length; int [][] dp = new int [n][2]; //dp[i][0]:表示第i天不持有时的最大利润 //dp[i][1]:表示第i天持有时的最大利润 dp[0][0] = 0; dp[0][1] = - prices[0]; //每种qing for(int i = 1 ; i < n ; i ++){ //不持有的两种状态推导 //1. 今天刚卖出去的。dp[i][0] = dp[i - 1][1] + price[i] //2. 之前卖出去的。 dp[i][0] = dp[i - 1][0] dp[i][0] = Math.max(dp[i - 1][1] + prices[i] , dp[i - 1][0]); //持有的两种状态推导 //1. 今天刚持有的。dp[i][1] = - price[i] //2. 之前就持有的。 dp[i][1] = dp[i - 1][1] dp[i][1] = Math.max(-prices[i] , dp[i - 1][1]); } return dp[n - 1][0]; } }
122. 买卖股票的最佳时机 II - 力扣(LeetCode)
现在变换问题:股票可以买卖多次,该怎么算?
本题的股票可以买卖多次,当第i天买入股票的时候,所得现金可能有之前买过的利润。
递推公式: dp[i][0]
表示第i天持有股票的最多现金。
第i- 1天持有股票,dp[i - 1][0]
。
第i天买入股票,(可能包含之前的利润)dp[i - 1][1] - prices[i]
dp[i][1]
表示第i天不持有股票的最多现金。
第i天不持有股票,dp[i - 1][1]
。
第i天卖出股票prices[i] + dp[i - 1][0]
class Solution {
public int maxProfit(int[] prices) {
int n = prices.length;
int [][] dp = new int [n][2];
dp[0][0] = 0;
dp[0][1] = - prices[0];
for(int i = 1 ; i < n ; i ++){
dp[i][0] = Math.max(dp[i - 1][1] + prices[i] , dp[i - 1][0]);
//唯一变化:持有的两种状态推导
//1. 今天刚持有的。dp[i][1] =dp[i - 1][0] - price[i]
dp[i][1] = Math.max(dp[i - 1][0]-prices[i] , dp[i - 1][1]);
}
return dp[n - 1][0];
}
}
123. 买卖股票的最佳时机 III - 力扣(LeetCode)
当股票只可以买卖两次时,应该怎么计算?
确定dp数组下标及其含义:
dp[i][j]
中i表示第i天,j为[0 - 4]五个状态,dp[i][j]
为第i天状态j所剩的最大现金。
五个状态为:
确定递推公式:
达到dp[i][1]
状态,有两个具体操作:
dp[i][1] = dp[i-1][0] - prices[i]
dp[i][1] = dp[i - 1][1]
一定是选最大的,所以 dp[i][1] = max(dp[i-1][0] - prices[i], dp[i - 1][1]);
同理可推出剩下状态部分:
dp[i][2] = max(dp[i - 1][1] + prices[i], dp[i - 1][2])
dp[i][3] = max(dp[i - 1][3], dp[i - 1][2] - prices[i]);
dp[i][4] = max(dp[i - 1][4], dp[i - 1][3] + prices[i]);
dp数组如何初始化
第0天没有操作,dp[0][0] = 0
;
第0天做第一次买入的操作,dp[0][1] = -prices[0]
;
第0天做第一次卖出的操作,(当天买入当天卖出)dp[0][2] = 0
;
第0天做第二次买入的操作,dp[0][3] = - prices[0]
;
第0天做第二次卖出的操作,dp[0][4] = 0
。
举例推导dp数组。
class Solution {
public int maxProfit(int[] prices) {
int n = prices.length ;
int [][] dp = new int [n][4];
//买入
dp[0][0] = - prices[0];
//卖出
dp[0][1] = 0;
//二次买入
dp[0][2] = -prices[0];
//二次卖出
dp[0][3] = 0;
for(int i = 1 ; i < n ; i ++){
//第一次买入分为两种情况
//之前买的 / 今天刚买
dp[i][0] = Math.max(dp[i - 1][0] , - prices[i]);
//第一次卖出分两种情况 之前卖出的 / 今天卖的
dp[i][1] = Math.max(dp[i - 1][1] ,dp[i - 1][0] + 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]);
}
return dp[n - 1][3];
}
}
*** - [188. 买卖股票的最佳时机 IV - 力扣(LeetCode)](https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iv/) **最多可以完成k笔交易,该怎么算?** 与最多完成两次交易类似,我们先找到完成两次交易的规律: 发现:2次交易我们确定了五种状态,那么k次交易,我们可以确定2 * k + 1次状态。 1. dp数组含义: `dp[i][0]`:第i天不做操作的最大金额。 `dp[i][1]`:第i天持有股票的最大金额。 `dp[i][2]`:第i天不持有股票的最大金额。 ······ 规律:j为奇数表示持有,j为偶数表示不持有。 递推公式: `dp[i][1] = max(dp[i - 1][0] - prices[i], dp[i - 1][1])`; `dp[i][2] = max(dp[i - 1][1] + prices[i], dp[i - 1][2])` 规律:j为偶数时:`dp[i][j] = max(dp[i - 1][j - 1] + prices[i] , dp[i - 1][j])`。 j为奇数时:`dp[i][j] = max(dp[i - 1][j - 1] - prices[i] , dp[i - 1][j])` dp数组初始化: 规律:j为奇数时,初始化为 `- prices[0]`。 遍历顺序:顺序遍历 举例推导。 ```java class Solution { public int maxProfit(int k, int[] prices) { int n = prices.length; int [][] dp = new int [n + 1][k * 2 + 1]; //初始化: for(int i = 1 ; i < k * 2; i +=2){ dp[0][i] = -prices[0]; } for(int i = 1;i < n ; i ++){ for(int j = 1 ;j < k * 2 + 1 ; j ++){ //j是奇数,是买入状态。 if(j % 2 == 1){ dp[i][j] = Math.max(dp[i - 1][j] ,dp[i - 1][j - 1] - prices[i]); } //j是偶数。就是卖出状态。 if(j % 2 == 0){ dp[i][j] = Math.max(dp[i - 1][j] , dp[i - 1][j - 1] + prices[i]); } } } return dp[n - 1][k * 2]; } }
309. 最佳买卖股票时机含冷冻期 - 力扣(LeetCode)
可以买卖多次,但是股票包含冷冻期,该怎么算?
该题存在四个状态
状态一:持有股票状态。
状态二:不持有股票,保持卖出股票的状态。
状态三:今天卖出股票。
为什么有这个状态?
为了表示冷冻状态,又单列出今天卖出状态,那么表示冷冻状态就是前一天是卖出状态。
也是为了卖出状态转为买入状态时,保证中间不会有冷冻期。
状态四:今天为冷冻期,但冷冻期只有一天。
递推公式:
达到买入股票状态(状态一)即:dp[i][0]
,有两个具体操作:
操作一:前一天就是持有股票状态(状态一),dp[i][0] = dp[i - 1][0]
操作二:今天买入了,有两种情况
dp[i - 1][3] - prices[i]
dp[i - 1][1] - prices[i]
即:dp[i][0] = max(dp[i - 1][0], dp[i - 1][3] - prices[i], dp[i - 1][1] - prices[i]);
达到保持卖出股票状态(状态二)即:dp[i][1]
,有两个具体操作:
操作一:前一天就是状态二
操作二:前一天是冷冻期(状态四),也就是冷冻期过了也没买。
即:dp[i][1] = max(dp[i - 1][1], dp[i - 1][3]);
达到今天就卖出股票状态(状态三),即:dp[i][2]
,只有一个操作:
即:dp[i][2] = dp[i - 1][0] + prices[i]
;
达到冷冻期状态(状态四),即:dp[i][3]
,只有一个操作:
即:dp[i][3] = dp[i - 1][2]
;
dp数组初始化:
持有股票状态(状态一):dp[0][0] = -prices[0]
。
不持有股票状态(状态二、三):dp[0][1] = 0;dp[0][2] = 0
。
达到冷冻期(状态四):dp[0][3] = 0
。
遍历顺序:从前往后遍历。
class Solution { public int maxProfit(int[] prices) { int n = prices.length; int [][] dp = new int [n][4]; //卖出状态 dp[0][0] = 0; //持有状态 dp[0][1] = - prices[0]; //今天卖出状态 dp[0][2] = 0; //今天为冷冻期 dp[0][3] = 0; for(int i = 1 ; i < n ; i++){ //流转到买入 dp[i][1] = Math.max(Math.max(dp[i - 1][1] , dp[i - 1][0] - prices[i]) , dp[i - 1][3] - prices[i]); //流转到卖出 dp[i][0] = Math.max(dp[i - 1][0] , dp[i - 1][3]); //流转到今天卖出 dp[i][2] = dp[i - 1][1] + prices[i]; //流转到冷冻 dp[i][3] = dp[i - 1][2]; } return Math.max(Math.max(dp[n - 1][0] , dp[n - 1][2]) , dp[n - 1][3]); } }
714. 买卖股票的最佳时机含手续费 - 力扣(LeetCode)
可以无限次买卖股票,但是包含手续费?
相对于动态规划:122.买卖股票的最佳时机II (opens new window),本题只需要在计算卖出操作的时候减去手续费就可以了,代码几乎是一样的。
class Solution {
public int maxProfit(int[] prices, int fee) {
int n = prices.length;
int [][] dp= new int [n + 1][2];
dp[0][1] = -prices[0];
dp[0][0] = 0;
for(int i = 1 ; i < n ; i ++){
dp[i][0] = Math.max(dp[i - 1][0] , prices[i] + dp[i - 1][1] - fee);
dp[i][1] = Math.max(dp[i - 1][1] , dp[i - 1][0] - prices[i]);
}
return dp[n - 1][0];
}
}
虽然算法很简单,但这种买卖股票问题算法是一种非常有用的工具。如果你希望了解更多关于这个算法的信息,建议你继续关注我的博客,我将分享更多有关这个话题的信息。
整理自:代码随想录
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。