1.leetcode_121.买卖股票的最佳时机
给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格。如果你最多只允许完成一笔交易(即买入和卖出一支股票),设计一个算法来计算你所能获取的最大利润。
注意你不能在买入股票前卖出股票。
示例 1:
输入:
[7,1,5,3,6,4]
输出:
5
解释: 在第 2 天(股票价格 = 1)的时候买入,在第 5 天(股票价格 = 6)的时候卖出,最大利润 = 6-1 = 5 。注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。
示例 2:
输入:
[7,6,4,3,1]
输出:
0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
2.解题思路
方法1:
方法2:动态规划
dp[i][0]代表第i+1天没有持股票,dp[i][1]代表第i+1天持有股票
初始化:
dp[0][0] = 0; 第一天没有持股,这时候相当于没有买入,故为0
dp[0][1] = -prices[0]; 第一天持股,相当于买入,这时候为-pricrs[0]
- 状态转移方程:
没有持股 =max(昨天没有持股今天维持现状 , 昨天持股,今天卖出)
dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1] + prices[i]);
持股 = max(昨天持股今天维持现状,(之前没有交易,今天买入))【因为只能完成一笔交易,故今天买入,则前面就相当于一直没有进行交易为利润为0】
dp[i][1] = Math.max(dp[i-1][1], -1 * prices[i])
3.代码
方法1:
1 | public static int maxProfit(int[] prices) { |
方法2:
1 | class Solution { |
拓展1
以上题目中的“只允许完成一笔交易” 变成 “可以完成无数比交易”
同:leetcode-122:买卖股票的最佳时机 https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/submissions/
动态规划:
dp[i][0]代表第i+1天没有持股票,dp[i][1]代表第i+1天持有股票
- 初始化:
- dp[0][0] = 0; 第一天没有持股,这时候相当于没有买入,故为0
- dp[0][1] = -prices[0]; 第一天持股,相当于买入,这时候为-prices[0]
状态转移方程:
没有持股 =max(昨天没有持股今天维持现状 , 昨天持股,今天卖出)
dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1] + prices[i]);
//持股 = max(昨天持股今天维持现状,(昨天没有持股,今天买入))【相对于之前,这里改变了】
    `dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] - prices[i]) `
代码
1 | public static int maxProfit(int[] prices) { |
拓展2:
在拓展1的基础上[可以完成无数比交易],每次 sell 之后要等一天才能继续交易。
同:leetcode-309:最佳买卖股票时机含冷冻期 https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/
动态规划:
dp[i][0]代表第i+1天没有持股票,dp[i][1]代表第i+1天持有股票
- 初始化:
- dp[0][0] = 0; //第1天没有持股,这时候相当于没有买入,故为0
- dp[1][0] =Math.max(0,prices[1]-prices[0]); //第2天没有持股,这时候max(第一天没持股,第一天持股第二天卖出)
- dp[0][1] = -prices[0]; //第1天持股维持,相当于买入,这时候为-prices[0]
- dp[1][1] = Math.max(-prices[0],-prices[1]);//第2天持股,这时候max(第一天持股维持,第一天没持股第二天买入)
状态转移方程:
没有持股 =max(昨天没有持股今天维持现状 , (昨天持股,今天卖出))
dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1] + prices[i]);
持股 = max(昨天持股今天维持现状,(前天没有持股,今天买入))即:第i天要买的时候,要从前天的状态进行判断
dp[i][1] = Math.max(dp[i-1][1], dp[i-2][0] - prices[i]);
代码
1 | public static int maxProfit4(int[] prices) { |
拓展3:
每次买入交易要支付手续费。
leetcode-714:买卖股票的最佳时机含手续费 https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/
动态规划
dp[i][0]代表第i+1天没有持股票,dp[i][1]代表第i+1天持有股票
初始化:
dp[0][0] = 0; 第一天没有持股,这时候相当于没有买入,故为0
dp[0][1] = -prices[0] - fee; 第一天持股,相当于买入,这时候为-prices[0] - fee ,本次以买入作为交易的开始,每次买入就扣除手续费,卖出的时候就不扣除手续费了。
状态转移方程:
没有持股 =max(昨天没有持股今天维持现状 , 昨天持股,今天卖出)【买入扣除手续费,卖出就不扣除了,因为买卖都完成才扣一次手续费】
dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1] + prices[i]);
持股 = max(昨天持股今天维持现状,(昨天没有持股,今天买入))
dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] - prices[i] - fee);
代码
1 | public static int maxProfit5(int[] prices,int fee) { |
拓展4:
以上题目中的“只允许完成一笔交易” 变成 “只允许完成2笔交易”
同: https://www.nowcoder.com/questionTerminal/3e8c66829a7949d887334edaa5952c28
已调试通过
同: leetcode-123. 买卖股票的最佳时机 III :https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iii/submissions/
动态规划
dp[i][k][0]代表第i+1天交易k次并且没有持股票,dp[i][k][1]代表第i+1天交易k次并且持有股票
初始化:
- dp[0][1][0] = 0; //第一天,交易次数为1,没持股,相当于就没买入
- dp[0][1][1] = -prices[0]; //第一天,交易次数为1,持股,相当于买入股票
- dp[0][2][0] = 0; //第一天,交易次数为2,没持股,相当于买入卖出买入卖出,没有盈利
- dp[0][2][1] = -prices[0]; //第一天,交易次数为2,持股,相当于买入再卖出(交易1次)再买入
- 状态转移方程:
第(i+1)天交易数为2,没持股 = max(前一天交易数为2没持股维持,前一天交易数为2持股今天卖出)
    `dp[i][2][0] = Math.max(dp[i-1][2][0],dp[i-1][2][1] + prices[i]);`
第(i+1)天交易数为2,持股 = 前一天交易数为2持股维持,前一天交易数为1没持股今天买入[买入之前必须卖出,故之前交易数应该为1而不是为2]
   `dp[i][2][1] = Math.max(dp[i-1][2][1],dp[i-1][1][0] - prices[i]);`
第(i+1)天交易数为1,没持股 = max(前一天交易数为1没持股维持,前一天交易数为1持股今天卖出)[卖出之前必须买入,故交易数为1而不是0]
   ` dp[i][1][0] = Math.max(dp[i-1][1][0],dp[i-1][1][1] + prices[i]);`
第(i+1)天交易数为1,持股 = max(前一天交易数为1持股维持,(没交易,今天买入))
    ` dp[i][1][1] = Math.max(dp[i-1][1][1],-1 * prices[i]);`
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23 > import java.util.*;
> public class Stock {
> public int maxProfit(int[] prices, int n) {
> if(prices.length == 0)
> return 0;
> //dp[i][k][0]代表第(i+1)天交易次数为k,没持股
> int dp[][][] = new int[prices.length][3][2];
> //初始化
> dp[0][1][0] = 0;
> dp[0][1][1] = -prices[0];
> dp[0][2][0] = 0;
> dp[0][2][1] = -prices[0];
> //动态规划
> for(int i = 1;i<prices.length;i++){
> dp[i][2][0] = Math.max(dp[i-1][2][0],dp[i-1][2][1] + prices[i]);
> dp[i][2][1] = Math.max(dp[i-1][2][1],dp[i-1][1][0] - prices[i]);
> dp[i][1][0] = Math.max(dp[i-1][1][0],dp[i-1][1][1] + prices[i]);
> dp[i][1][1] = Math.max(dp[i-1][1][1],-1 * prices[i]);
> }
> return dp[prices.length-1][2][0];
> }
> }
>
拓展5:
以上题目中的“只允许完成一笔交易” 变成 “只允许完成k笔交易”
leetcode-188: 买卖股票的最佳时机IV:https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iv/
动态规划:
dp[i][k][0]代表第i+1天交易k次并且没有持股票,dp[i][k][1]代表第i+1天交易k次并且持有股票
- 初始化:
- dp[0][i][0] = 0; 【i为交易成交的笔数】即第一天,持续的买入卖出买入卖出,没收益
- dp[0][i][1] = -prices[0]; 【i为交易成交的笔数】即第一天,持续的买入卖出买入,收益为买入的-prices[0]
状态转移方程:
第(i+1)天交易数为j,没持股 = max(前一天交易数为j没持股维持,前一天交易数为j持股今天卖出)
    ` dp[i][j][0] = Math.max(dp[i-1][j][0], dp[i-1][j][1] + prices[i]);`
第(i+1)天交易数为j,持股 = max(前一天交易数为j持股维持,前一天交易数为j没持股今天买入)
    `dp[i][j][1] = Math.max(dp[i-1][j][1], dp[i-1][j-1][0] - prices[i]);`
答案超出内存限制:
1 | class Solution { |
有时间再想想,觉得思路应该是对的,但是这些题应该有更优的解法,动态规划时间复杂度还是有点高的。
整理自:https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/solution/yi-ge-fang-fa-tuan-mie-6-dao-gu-piao-wen-ti-by-l-3/