image.png

思路

分析dp数组含义,这里的第二维代表的是五种状态:

  1. 不操作
  2. 第一次买入
  3. 第一次卖出
  4. 第二次买入
  5. 第二次卖出

每一种状态的递推公式跟之前的题目类似,要么维持前一天的状态,要么加减股票价格,具体看代码即可理解。
最大利润总是在卖出股票的时候,所以最后输出的第二次卖出的结果,即状态4

  1. var maxProfit = function(prices) {
  2. // 五种状态,0是不操作,奇数买入,偶数卖出
  3. let dp =new Array(prices.length).fill(0).map(x=> new Array(5).fill(0))
  4. dp[0][1] =-prices[0] //第一次买入
  5. dp[0][3] =-prices[0] //第二次买入
  6. for(let i=1;i<prices.length;i++){
  7. dp[i][0] =dp[i-1][0]
  8. dp[i][1] =Math.max(dp[i-1][1],dp[i-1][0]-prices[i])
  9. dp[i][2] =Math.max(dp[i-1][2],dp[i-1][1]+prices[i]) //第一次卖出
  10. dp[i][3] =Math.max(dp[i-1][3],dp[i-1][2]-prices[i])
  11. dp[i][4] =Math.max(dp[i-1][4],dp[i-1][3]+prices[i]) //第二次卖出
  12. }
  13. return dp[prices.length-1][4]
  14. };