题目
给定一个整数数组prices
,其中第 prices[i]
表示第 *i*
天的股票价格 。
设计一个算法计算出最大利润。在满足以下约束条件下,你可以尽可能地完成更多的交易(多次买卖一支股票):
- 卖出股票后,你无法在第二天买入股票 (即冷冻期为 1 天)。
注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。
解题思路
动态规划——这题必须膜拜大神
正文:
因为当天卖出股票实际上也是属于“不持有”的状态,那么第i天如果不持有,那这个“不持有”就有了两种状态:1.本来就不持有,指不是因为当天卖出了才不持有的;2.第i天因为卖出了股票才变得不持有
而持有股票依旧只有一种状态
所以对于每一天i,都有可能是三种状态:
0.不持股且当天没卖出,定义其最大收益dp[i][0]
;
1.持股,定义其最大收益dp[i][1]
;
2.不持股且当天卖出了,定义其最大收益dp[i][2]
;
初始化:
dp[0][0]=0;
//本来就不持有,啥也没干
dp[0][1]=-1*prices[0];
//第0天只买入
dp[0][2]=0;
//可以理解成第0天买入又卖出,那么第0天就是“不持股且当天卖出了”这个状态了,其收益为0,所以初始化为0是合理的
重头戏:
一、第i天不持股且没卖出的状态dp[i][0]
,也就是我没有股票,而且还不是因为我卖了它才没有的,那换句话说是从i-1天到第i天转移时,它压根就没给我股票!所以i-1天一定也是不持有,那就是不持有的两种可能:i-1天不持股且当天没有卖出dp[i-1][0]
;i-1天不持股但是当天卖出去了dp[i-1][2]
;
所以: dp[i][0]=max(dp[i-1][0],dp[i-1][2])
二、第i天持股dp[i][1]
,今天我持股,来自两种可能:
1、要么是昨天我就持股,今天继承昨天的,也就是dp[i-1][1]
,这种可能很好理解;
2、要么:是昨天我不持股,今天我买入的,但前提是昨天我一定没卖!因为如果昨天我卖了,那么今天我不能交易!也就是题目中所谓“冷冻期”的含义,只有昨天是“不持股且当天没卖出”这个状态,我今天才能买入!所以是dp[i-1][0]-p[i]
所以: dp[i][1]=max(dp[i-1][1],dp[i-1][0]-p[i])
三、i天不持股且当天卖出了,这种就简单了,那就是说昨天我一定是持股的,要不然我今天拿什么卖啊,而持股只有一种状态,昨天持股的收益加上今天卖出得到的新收益,就是dp[i-1][1]+p[i]
啦
所以:dp[i][2]=dp[i-1][1]+p[i]
总结:最后一天的最大收益有两种可能,而且一定是“不持有”状态下的两种可能,把这两种“不持有”比较一下大小,返回即可
代码
class Solution {
public int maxProfit(int[] prices) {
int length=prices.length;
if(length==1){
return 0;
}
int[][] dp=new int[length][3];
//不持有且当天没卖出
dp[0][0]=0;
//持有
dp[0][1]=-1*prices[0];
//不持有且当天卖出
dp[0][2]=0;
for(int i=1;i<length;i++){
dp[i][0]=Math.max(dp[i-1][0],dp[i-1][2]);
dp[i][1]=Math.max(dp[i-1][1],dp[i-1][0]-prices[i]);
dp[i][2]=dp[i-1][1]+prices[i];
}
return Math.max(dp[length-1][0],dp[length-1][2]);
}
}
标签:持股,309,持有,力扣,int,最佳时机,prices,卖出,dp
From: https://www.cnblogs.com/always-uie/p/18175228