309. 最佳买卖股票时机含冷冻期

  1. dp定义

dp[i][j]，第i天状态为j，所剩的最多现金为dp[i][j]。
我们目前持有一支股票，对应的「累计最大收益」记为 dp[i][0]；
我们目前不持有任何股票，（今天卖出了），对应的「累计最大收益」记为 dp[i][1]；
我们目前不持有任何股票，不是今天卖出的（处于冷冻期或者冷冻期过了没买入），对应的「累计最大收益」记为 dp[i][1]；

  1. 转移方程
  • dp[i][0] = max(dp[i - 1][0], dp[i - 1][2] - prices[i]);（前一天就持有，或者前一天不是卖出，今天再买入）
  • dp[i][1] = dp[i - 1][0] + prices[i];（前一天持有，在今天卖出了）
  • dp[i][2] = max(dp[i - 1][1],dp[i-1][2]); （昨天卖出了或者，昨天是卖出之后的）
    1. class Solution {
    2. public:
    3.   int maxProfit(vector<int>& prices) {
    4.       int n = prices.size();
    5.       if (n == 0) return 0;
    6.       vector<vector<int>> dp(n, vector<int>(3, 0));
    7.       dp[0][0] = -prices[0]; // 持股票
    8.       for (int i = 1; i < n; i++) {
    9.           dp[i][0] = max(dp[i - 1][0],  dp[i - 1][2] - prices[i]);
    10.           dp[i][1] = dp[i - 1][0] + prices[i];
    11.           dp[i][2] = max(dp[i - 1][1],dp[i-1][2]);
    12.       }
    13.       return max(dp[n - 1][1], dp[n - 1][2]);
    14.   }
    15. };