[Algorihm][简单多状态DP问题][买卖股票的最佳时机含冷冻期][买卖股票的最佳时机含手续费]详细讲解

---

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

• 1.题目链接

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

2.算法原理详解

• 思路：

  • 确定状态表示 -> dp[i][j]的含义：i -> 到了哪天，j -> 当天处于什么状态

    • dp[i][0]：第i天结束之后，处于"买入"状态，此时的最大利润
    • dp[i][1]：第i天结束之后，处于"可交易"状态，此时的最大利润
    • dp[i][2]：第i天结束之后，处于"冷冻期"状态，此时的最大利润

  • 推导状态转移方程：本题关系复杂，可以画图辅助

    • dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - p[i])
    • dp[i][1] = max(dp[i - 1][1], dp[i - 1][2])
    • dp[i][2] = dp[i - 1][0] + p[i]
      

  • 初始化：

    • dp[0][0] = -p[0], dp[0][1] = dp[0][2] = 0

  • 确定填表顺序：从左往右，一次填写三个表

  • 确定返回值：max(dp[n - 1][1], dp[n - 2][2])

---

3.代码实现

int maxProfit(vector<int>& prices) 
{int n = prices.size();vector<vector<int>> dp(n, vector<int>(3));dp[0][0] = -prices[0];for(int i = 1; i < n; 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][2]);dp[i][2] = dp[i - 1][0] + prices[i];}return max(dp[n - 1][1], dp[n - 1][2]);
}

---

2.买卖股票的最佳时机含手续费

1.题目链接

• 买卖股票的最佳时机含手续费

---

2.算法原理详解

• 思路：

  • 确定状态表示 -> dp[i]的含义

    • 第i天结束之后，所能获得的最大利润
    • 本题，状态表示还可以继续细分：
      • f[i]：第i天结束之后，处于“买入”状态，此时的最大利润
      • g[i]：第i天结束之后，处于“卖出”状态，此时的最大利润
        

  • 推导状态转移方程：本题关系复杂，可以画图辅助

    • f[i] = max(f[i - 1], g[i - 1] - p[i])
    • g[i] = max(g[i - 1], f[i - 1] + p[i] - fee)
      

  • 初始化：

    • f[0] = -p[0], g[0] = 0

  • 确定填表顺序：从左往右，两个表一起填

  • 确定返回值：g[n - 1]

---

3.代码实现

int maxProfit(vector<int>& prices, int fee) 
{int n = prices.size();vector<int> f(n); // 买入vector<int> g(n); // 卖出f[0] = -prices[0];for(int i = 1; i < n; i++){f[i] = max(f[i - 1], g[i - 1] - prices[i]);g[i] = max(g[i - 1], f[i - 1] + prices[i] - fee);}return g[n - 1];
}