思路
分析dp数组含义,这里的第二维代表的是五种状态:
- 不操作
- 第一次买入
- 第一次卖出
- 第二次买入
- 第二次卖出
每一种状态的递推公式跟之前的题目类似,要么维持前一天的状态,要么加减股票价格,具体看代码即可理解。
最大利润总是在卖出股票的时候,所以最后输出的第二次卖出的结果,即状态4
var maxProfit = function(prices) {
// 五种状态,0是不操作,奇数买入,偶数卖出
let dp =new Array(prices.length).fill(0).map(x=> new Array(5).fill(0))
dp[0][1] =-prices[0] //第一次买入
dp[0][3] =-prices[0] //第二次买入
for(let i=1;i<prices.length;i++){
dp[i][0] =dp[i-1][0]
dp[i][1] =Math.max(dp[i-1][1],dp[i-1][0]-prices[i])
dp[i][2] =Math.max(dp[i-1][2],dp[i-1][1]+prices[i]) //第一次卖出
dp[i][3] =Math.max(dp[i-1][3],dp[i-1][2]-prices[i])
dp[i][4] =Math.max(dp[i-1][4],dp[i-1][3]+prices[i]) //第二次卖出
}
return dp[prices.length-1][4]
};