309.最佳买卖股票时机含冷冻期
看完题后的思路
-
dp[i][]
0: 第i天不持有股票的最大利润
1: 持有 -
递推公式
dp[i][0]=max(第i-1天不持有,第i-1天持有,在第i天卖了)
dp[i][1]=max(第i-1天持有, 第i-2天不持有,第i天持有) -
初始化
dp[0][0]=0;
dp[0][1]=-price[i];
dp[1][0]=max(x,x)
dp[1][1]=max(-price[0],=price[1])
代码
public int maxProfit04(int[] prices) {
if (prices.length==1){
return 0;
}
int[][] dp=new int[prices.length][2];
dp[0][0]=0;
dp[0][1]=-prices[0];
dp[1][0]=Math.max(dp[0][0],dp[0][1]+prices[1]);
dp[1][1]=Math.max(dp[0][1],-prices[1]);
for (int i = 2; i <prices.length ; i++) {
dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]+prices[i]);
dp[i][1]=Math.max(dp[i-1][1],dp[i-2][0]-prices[i]);
}
return Math.max(dp[dp.length-1][0],dp[dp.length-1][1]);
}
看题接的收货
每天其实有四个状态
(1)今天持有股票 dp[i][3]=max(dp[i-1][3],dp[i][1]-price[i],dp[i][2]-price[i])
今天不持有股票
(2)今天卖出股票 dp[i][0] =dp[i-1][3]+price[i]
(3)今天是冷冻期(前天卖出股票) dp[i][1]=dp[i-1][0]
(3)今天不是冷冻期(两天前卖出股票) dp[i][2]=max(dp[i-1][2],dp[i-1][1])
初始化
dp[0][0]=0; // -1天买入,今天卖出
dp[0][1]=0; // 今天是冷冻期,-1天卖出,钱为0
dp[0][2]=0; // -1天为0,今天也是0
dp[0][3]=-price[0];
714.买卖股票的最佳时机含手续费
看完题目的思路
设卖出的时候付手续费
-
dp[i][]
0: 第i天不持有股票的最大利润
1: 持有 -
递推公式
dp[i][0]=max(dp[i-1][0],dp[i-1][1]+price[i]-fee)
dp[i][1]=max(dp[i-1][1],dp[i-1][0]=price[i]) -
初始化
dp[0][0]=0;
dp[0][1]=-price[i];
代码
public int maxProfit(int[] prices, int fee) {
int[][] dp=new int[prices.length][2];
dp[0][0]=0;
dp[0][1]=-prices[0];
for (int i = 1; i <prices.length ; i++) {
dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]+prices[i]-fee);
dp[i][1]=Math.max(dp[i-1][1],dp[i-1][0]-prices[i]);
}
return Math.max(dp[dp.length-1][0],dp[dp.length-1][1]);
}
