给定一个整数数组prices,其中第 prices[i] 表示第 i 天的股票价格 。
设计一个算法计算出最大利润。在满足以下约束条件下,你可以尽可能地完成更多的交易(多次买卖一支股票):
卖出股票后,你无法在第二天买入股票 (即冷冻期为 1 天)。 注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。
示例 1:
输入: prices = [1,2,3,0,2] 输出: 3 解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]
示例 2:
输入: prices = [1] 输出: 0
提示:
1 <= prices.length <= 5000 0 <= prices[i] <= 1000
对于此类简单多状态dp问题,先需要确定dp[i]表示的含义:dp[i]表示第i天的最大利润。
当处于第i天时,有三种状态:
故我们需要设置dp表为dp[n][3]。
对于这三种状态,我们可以得知的状态转化为:
即,状态转移方程为:
初始化过程: 对于第一天,可以选择购买股票进入有股票状态,也可以选择不购买股票,进入无股票,但不处于冷冻期状态。
最终的返回值是取这三种状态下的最大值。
class Solution {
public int maxProfit(int[] prices) {
int n = prices.length;
int[][] dp = new int[n][3];
dp[0][0] = prices[0]*(-1);
for(int i=1;i<n;i++){
dp[i][0] = Math.max(dp[i-1][0],dp[i-1][2]-prices[i]);
dp[i][1] = dp[i-1][0]+prices[i];
dp[i][2] = Math.max(dp[i-1][2],dp[i-1][1]);
}
return Math.max(Math.max(dp[n-1][1],dp[n-1][2]),dp[n-1][0]);
}
}
提交截图:
这篇博客如果对你有帮助,给博主一个免费的点赞以示鼓励,欢迎各位🔎点赞👍评论收藏⭐,谢谢!!!