#Java #动态规划
Feeling and experiences:
给定一个整数数组prices
,其中第??prices[i]
?表示第?i
?天的股票价格 。?
设计一个算法计算出最大利润。在满足以下约束条件下,你可以尽可能地完成更多的交易(多次买卖一支股票):
注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。
示例 1:
输入: prices = [1,2,3,0,2] 输出: 3 解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]
同理,还是得定义状态
该题多了一个条件:冷冻期
其本质还是一样的
class Solution {
public int maxProfit(int[] prices) {
if (prices == null || prices.length < 2) {
return 0;
}
//股票问题,但是多了一个条件:冷冻期
//创建dp数组
int [][]dp = new int[prices.length][2];
//定义3种状态
//1.持有股票状态 2.不持有股票状态:头一天为冷冻期,或者头一天卖出 , 或者今天持有股票,今天卖掉股票
//3.进入冷冻期
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公式
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 dp[prices.length - 1][0];
}
}
?初始化第一天的状态 dp[0][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]);? (持有股票,可能是前一天就持有,或者前两天不持有今天持有)
给定一个整数数组?prices
,其中 prices[i]
表示第?i
?天的股票价格 ;整数?fee
代表了交易股票的手续费用。
你可以无限次地完成交易,但是你每笔交易都需要付手续费。如果你已经购买了一个股票,在卖出它之前你就不能再继续购买股票了。
返回获得利润的最大值。
注意:这里的一笔交易指买入持有并卖出股票的整个过程,每笔交易你只需要为支付一次手续费。
示例 1:
输入:prices = [1, 3, 2, 8, 4, 9], fee = 2 输出:8 解释:能够达到的最大利润: 在此处买入?prices[0] = 1 在此处卖出 prices[3] = 8 在此处买入 prices[4] = 4 在此处卖出 prices[5] = 9 总利润:?((8 - 1) - 2) + ((9 - 4) - 2) = 8
还是股票问题:要交手续费
该题和股票问题二几乎一样,只不过多了手续费
在那道题的基础上,把手续费即可
class Solution {
public int maxProfit(int[] prices, int fee) {
//这道题和之前的股票问题二几乎是一样的
//只不过要交手续费,把手续费算上去就行了
//创建dp数组
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 dp[prices.length-1][0];
}
}
dp[i][0]
表示第 i
天不持有股票时的最大利润,可以是前一天也不持有,或者前一天持有今天卖出(减去手续费)。dp[i][1]
表示第 i
天持有股票时的最大利润,可以是前一天就持有,或者前一天不持有今天买入。舟遥遥以轻扬,
风飘飘而吹衣。
Fighting!