代码随想录:动态规划｜309.最佳买卖股票时机含冷冻期

309. Best Time to Buy and Sell Stock with Cooldown

股票问题的核心：分清楚状态和状态如何转化的。

dp存储状态：持有和不持有的两个状态，细分为4个状态。

• 持有状态: 0.今天买入或已经买入
• 不持有状态: 1.今天卖出
  2.冷冻期 (昨日卖出)
  3.过了冷冻期 (早已卖出

而后还可以合并为3个状态，将dp[1]和dp[2]合并为一个状态。 即：不持有 = 没过冷冻期+过了冷冻期。 怎么好理解怎么去想。而且你完全可以把持有状态换成买入状态。

/**
 * @file 309. Best Time to Buy and Sell Stock with Cooldown.cpp
 * @brief Best Time to Buy and Sell Stock with Cooldown
 * can complete many transactions but must sell the stock before buy again.
 * \attention cooldown one day
 * @author Chris
 * @date 2023-12-28
 * @see https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-cooldown/description/
 */

#define DOCTEST_CONFIG_IMPLEMENT_WITH_MAIN
#include <algorithm>
#include <iostream>
#include <vector>
#include "../include/doctest.h"

using namespace std;

class Solution {
 public:
  /**
   * @brief 动态规划
   * 状态： 持有状态: 0.今天买入,或已经买入
   *     不持有状态: 1.今天卖出
   *               2.冷冻期 (昨日卖出)
   *               3.过了冷冻期 (早已卖出)
   */
  int maxProfit(vector<int> &prices) {
    int n = prices.size();
    vector<vector<int>> dp(n, vector<int>(4));
    dp[0][0] = -prices[0];
    for (int i = 1; i < n; ++i) {
      /* 0.持有 = 已经持有，继续保持状态 ｜(昨日冷冻期or过了冷冻期)今天买 */
      dp[i][0] = max(dp[i - 1][0], max(dp[i - 1][2], dp[i - 1][3]) - prices[i]);
      /* 1.今日卖出 = 昨日持有，今天卖 */
      dp[i][1] = dp[i - 1][0] + prices[i];
      /* 2.冷冻期 = 昨日卖出 */
      dp[i][2] = dp[i - 1][1];
      /* 3.过了冷冻期 = 昨天过了冷冻期，继续处于这个状态｜昨日冷冻期 */
      dp[i][3] = max(dp[i - 1][3], dp[i - 1][2]);
    }
    return *max_element(dp.back().begin() + 1, dp.back().end());
  }
};
/// @fn test function
TEST_CASE("Testing function") {
  Solution s;
  SUBCASE("case 1") {
    vector<int> prices1 = {1, 2, 3, 0, 2};
    CHECK(s.maxProfit(prices1) == 3);
  }
  SUBCASE("case 2") {
    vector<int> prices2 = {1};
    CHECK(s.maxProfit(prices2) == 0);
  }
}

vscode编辑器，doxygen document插件自动生成的doxygen注释语法
使用的doctest.h单元测试库
clangd语言服务器
代码风格clang-format格式based Google

714. Best Time to Buy and Sell Stock with Transaction Fee

这一题很简单，就加了个一个手续费。

dp[i]含义 第i天手里最大现金

两个状态：

• dp[i][0]持有状态
• dp[i][1]不持有股票状态

递推公式: 卖的时候交手续费

• 持有： 1。保持持有状态 2。昨天不持有，今天买入
  dp[i][0] = max(dp[i-1][0], dp[i][1] - prices[i])
• 不持有： 1。保持不持有状态 2。昨天持有，今天卖出。
  dp[i][1] = max(dp[i-1][1], dp[i][0] + prices[i] - fee)

初始化：

第一天买入 dp[0][0] = -prices[0]
dp[0][1] = 0;

递推顺序：第二天开始从前往后

/**
 * @file 714. Best Time to Buy and Sell Stock with Transaction Fee.cpp
 * @brief 714. Best Time to Buy and Sell Stock with Transaction Fee
 * \attention have transaction fee
 * @author Chris
 * @date 2023-12-28
 * @see https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/
 */
#include <vector>
using namespace std;
class Solution {
 public:
  int maxProfit(vector<int>& prices, int fee) {
    vector<vector<int>> dp(prices.size(), vector<int>(2));
    // dp[i][0] 持有股票, dp[i][1] 不持有股票
    dp[0][0] = -prices[0];
    for (int i = 1; i < prices.size(); ++i) {
      //  持有  = 保持持有状态 ｜ 不持有，今日买入
      dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
      // 不持有 = 保持不持有状态 ｜ 持有状态，今日卖出 - 手续费
      dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i] - fee);
    }
    return dp.back().back();
  }
};