江门网站建设服务,网站引流推广怎么做,北京网站建设东轩seo,移动应用开发实训报告目录题目思路动态规划题目来源 309. 最佳买卖股票时机含冷冻期
题目思路
每天最多只可能有三种状态中的一种
0表示当前处于买入状态(持有股票) 1表示当前处于卖出状态(不持有股票) 2表示当前处于冷冻状态 设dp[i][j]表示i - 1天状态为j时所拥有的最大现金 dp[i][0] Math.ma…
目录题目思路动态规划题目来源 309. 最佳买卖股票时机含冷冻期
题目思路
每天最多只可能有三种状态中的一种
0表示当前处于买入状态(持有股票) 1表示当前处于卖出状态(不持有股票) 2表示当前处于冷冻状态 设dp[i][j]表示i - 1天状态为j时所拥有的最大现金 dp[i][0] Math.max(dp[i-1][0],dp[i-1][2]-prices[i]); //持有股票dp[i][1] Math.max(dp[i-1][1],dp[i-1][0]prices[i]); //不持有股票dp[i][2] dp[i-1][1]; //冷冻期dp[i][0] Math.max(dp[i-1][0],dp[i-1][2]-prices[i])意思是你只有在股票冷冻期之后才能买入 dp[i][2] dp[i-1][1]意思是冷冻期肯定是卖出的状态(手上没有股票)
动态规划
1.确定dp数组以及下标的含义
dp[i][j]第i天状态为j所剩的最多现金为dp[i][j]。
可以定义下面三个状态 0表示当前处于买入状态(持有股票) 1表示当前处于卖出状态(不持有股票) 2表示当前处于冷冻状态 设dp[i][j]表示i - 1天状态为j时所拥有的最大现金
2.确定递推公式
买入状态 操作一前一天就是持有股票状态状态一dp[i][0] dp[i - 1][0] 操作二冷冻期之后才能买 dp[i][0] dp[i-1][2]-prices[i] dp[i][0] Math.max(dp[i-1][0],dp[i-1][2]-prices[i]); 卖出状态 操作一前一天就是卖出状态dp[i][1] dp[i - 1][1] 操作二持有股票才能卖出dp[i][1] dp[i-1][0]prices[i] dp[i][1] Math.max(dp[i-1][1],dp[i-1][0]prices[i]); 冷冻状态 只有卖出的状态 dp[i][2] dp[i-1][1];
3.dp数组如何初始化
如果是持有股票状态那么dp[0][0] -prices[0]一定是当天买入股票。 如果是不持有股票状态dp[0][1] 0当天买当天卖 如果是冷冻期状态dp[0][2] 0,延续不持有股票的状态
4.确定遍历顺序
从递归公式上可以看出dp[i] 依赖于 dp[i-1]所以是从前向后遍历。
5.举例推导dp数组
以 [1,2,3,0,2] 为例dp数组如下 代码实现
class Solution {public int maxProfit(int[] prices) {if(prices null || prices.length 0){return 0;}int[][] dp new int[prices.length][3];dp[0][0] -prices[0];dp[0][1] 0;dp[0][2] 0;for(int i 1;iprices.length;i){dp[i][0] Math.max(dp[i-1][0],dp[i-1][2]-prices[i]); //持有股票dp[i][1] Math.max(dp[i-1][1],dp[i-1][0]prices[i]); //不持有股票dp[i][2] dp[i-1][1]; //冷冻期}return Math.max(dp[prices.length-1][1],dp[prices.length-1][2]);}
}
