【java】力扣 买卖股票的最佳时机 动态规划
题目链接
题目描述
思路
本题主要用到了动态规划
1.先定义dp数组的含义
先定义一个二维数组dp
然后dp[i][0]来表示第i天持有股票的现金
dp[i][1]代表第i天不持有股票的现金
刚开始的现金为0,当第i天买入时,现金就成为了-prices[i]
设置成"持有",“持有”不代表是当天买入,有可能是之前买入 而保持持有的状态
2.递归公式
dp[i][0] = max(dp[i-1][0],-prices[i]);
**dp[i-1][0]**表示的是在i-1天就持有股票,一直保持持有的状态
-prices[i] 表示的是当天买入的股票后的现金
同理,
dp[i][1] =max(dp[i-1][1],prices[i]+dp[i-1][0])
**dp[i-1][1]**表示的是第i-1天就不持有股票,然后保持原状,所得现金就是昨天不持有股票的所得现金
prices[i]+dp[i-1][0] 表示的是当天卖出的股票所得的现金
3.初始化
dp[0][0] =-prices[0]
刚开始就买入股票,初始金钱是0,然后买入之后,就成-prices[0]
dp[0][1] = 0 刚开始没有任何操作 初始现金是0;
4.遍历数组
因为dp[i]都是由dp[i-1]推导出来的,所以我们由前向后遍历
分析完毕
上代码
代码
public int maxProfit(int[] prices) {
//动态规划
if(prices ==null || prices.length==0){
return 0;
}
int n =prices.length;
//dp[i][0]表示第i天持有股票
//dp[i][1]表示第i天不持有股票
int[][] dp =new int[n][2];
//初始化
//刚开始就买入股票,初始金钱是0,然后买入之后,就成-prices[0]
dp[0][0]=-prices[0];
dp[0][1] =0;
//开始遍历数组
for(int i=1;i<n;i++){
dp[i][0] = Math.max(dp[i-1][0],-prices[i]);
dp[i][1] = Math.max(dp[i-1][1],dp[i-1][0]+prices[i]);
}
return dp[n-1][1];
}
感谢大家的收看!!!
这种类型的其他例题请看
【java】力扣 买卖股票的最佳时机II
原文地址:https://blog.csdn.net/qq_55846232/article/details/140450963
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!