动态规划之股票系列
123. 交易股票的最佳机遇 III188. 交易股票的最佳机遇 IV
309. 交易股票的最佳机遇含冷冻期
1.AC代码:
class Solution {
public int maxProfit(int[] prices) {
int n=prices.length;
int[][] dp=new int;
dp=-prices;
dp=-prices;
for(int i=1;i<n;i++){
// 第一次买入
dp=Math.max(dp,-prices);
// 第一次卖出
dp=Math.max(dp,dp+prices);
// 第二次买入
dp=Math.max(dp,dp-prices);
// 第二次卖出
dp=Math.max(dp,dp+prices);
}
return dp;
}
} 题目限制了最多只能完成两笔交易业务(必要注意的是这里说的一笔交易业务是指买入和卖出两个动作,后续的题目也都是这个意思),dp代表的是第i天的j状态下持有的金额为dp.
这个题目中dp代表的是第i天是第一次买入(或者可以说是第一次持有股票),dp代表的是第一次卖出股票(或第一次不持有股票的状态),dp代表的是第二次持有股票的状态,dp代表的是第二次不持有股票的状态.
2.AC代码:
class Solution {
public int maxProfit(int k, int[] prices) {
if(prices.length==0) return 0;
int n=prices.length;
int[][] dp=new int;
for(int i=1;i<k*2;i+=2){
dp=-prices;
}
for(int i=1;i<n;i++){
for(int j=0;j<k*2-1;j+=2){
// 奇数买入
dp=Math.max(dp,dp-prices);
// 偶数卖出
dp=Math.max(dp,dp+prices);
}
}
return dp;
}
} 这个题和上面谁人题目很雷同,上面谁人题是这个题中的一个,也就是说k=2的情况,仍然是一样的,一次交易业务分为两个动作(买入,卖出)以是k次交易业务的状态为k*2个.在这里我们下标0代表没有动作,下表为奇数代表买入,偶数代表卖出.
3.AC代码:
class Solution {
public int maxProfit(int[] prices) {
int n=prices.length;
if(n==0) return 0;
int[][] dp=new int;
dp=-prices;
for(int i=1;i<n;i++){
// 持有股票
dp=Math.max(dp,Math.max(dp-prices,dp-prices));
// 不持有股票
dp=Math.max(dp,dp);
// 状态三当天买出不能和状态2（步持有股票）合并，因为卖出股票后面紧接着的状态就是冻结！
// 当天卖出
dp=dp+prices;
// 冻结期
dp=dp;
}
return Math.max(dp, Math.max(dp, dp));
}
} 根据题目要求,我们可以将交易业务分为四个状态(持有,不持有,当日卖出,冷冻期),在这里必要注意的是,由于卖出股票的后一天肯定会进入冷冻期,以是,在这里我们将当日卖出的操纵从不持有股票这一大类中单独划出,这样更方便理解.
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]