---

1.買賣股票的最佳時(shí)機(jī)含冷凍期

• 1.題目鏈接

買賣股票的最佳時(shí)機(jī)含冷凍期

2.算法原理詳解

• 思路：

  • 確定狀態(tài)表示 -> dp[i][j]的含義：i -> 到了哪天，j -> 當(dāng)天處于什么狀態(tài)

    • dp[i][0]：第i天結(jié)束之后，處于"買入"狀態(tài)，此時(shí)的最大利潤
    • dp[i][1]：第i天結(jié)束之后，處于"可交易"狀態(tài)，此時(shí)的最大利潤
    • dp[i][2]：第i天結(jié)束之后，處于"冷凍期"狀態(tài)，此時(shí)的最大利潤

  • 推導(dǎo)狀態(tài)轉(zhuǎn)移方程：本題關(guān)系復(fù)雜，可以畫圖輔助

    • 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

  • 確定填表順序：從左往右，一次填寫三個(gè)表

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

---

3.代碼實(shí)現(xiàn)

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.買賣股票的最佳時(shí)機(jī)含手續(xù)費(fèi)

1.題目鏈接

• 買賣股票的最佳時(shí)機(jī)含手續(xù)費(fèi)

---

2.算法原理詳解

• 思路：

  • 確定狀態(tài)表示 -> dp[i]的含義

    • 第i天結(jié)束之后，所能獲得的最大利潤
    • 本題，狀態(tài)表示還可以繼續(xù)細(xì)分：
      • f[i]：第i天結(jié)束之后，處于“買入”狀態(tài)，此時(shí)的最大利潤
      • g[i]：第i天結(jié)束之后，處于“賣出”狀態(tài)，此時(shí)的最大利潤
        

  • 推導(dǎo)狀態(tài)轉(zhuǎn)移方程：本題關(guān)系復(fù)雜，可以畫圖輔助

    • 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è)表一起填

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

---

3.代碼實(shí)現(xiàn)

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];
}