---

前言

在本文章中，我們將要詳細介紹一下Leetcode中買賣股票的最佳時機含冷凍期相關的內容，本題采用動態規劃的思想解決

一、題目分析

二、算法原理

1.狀態表示

列出dp表，dp表中值的含義是什么
? ?dp[i]表示第i天之后此時的最大利潤
由于第i天不確定具體狀態，多狀態dp問題
? ? 🌟 .dp[i][0]:手中有股票沒有賣出，我們簡單稱為買入狀態，此時的最大利潤
? ? 🌟 .dp[i][1]:處于冷凍期，無法購買股票，我們稱為冷凍期，此時的最大利潤
? ? 🌟 .dp[i][2]:手中沒有股票，也不處于冷凍期，此時的最大利潤

2.狀態轉移方程

根據最近一步劃分問題

根據狀態表示，我們可以劃分為9種不同的轉換
? ? 🌟 .(i-1)天處于買入狀態，第i天處于買入狀態:這個是可以的，這一天啥也不干
? ? 🌟 .(i-1)天處于買入狀態，第i天處于冷凍期狀態:這個可以，就是這天把股票賣了，賺了錢，需要加上prices[i]的值（涉及利潤）
? ? 🌟 .(i-1)天處于買入狀態，第i天處于正常狀態:這個不可以，你手中有股票，不處于正常狀態，即使把股票賣了，也得先經過冷凍期才可以
? ? 🌟 .(i-1)天處于冷凍期狀態，第i天處于冷凍期狀態:這個不可以，冷凍期只能有一天
? ? 🌟 .(i-1)天處于冷凍期狀態，第i天處于買入狀態:這個不可以，冷凍期是不能買股票的
? ? 🌟 .(i-1)天處于冷凍期狀態，第i天處于正常狀態:這個可以，經過一天之后進入正常狀態。
? ? 🌟 .(i-1)天處于正常狀態，第i天處于正常狀態:這個可以，感覺這個股票不好，等一等再買
? ? 🌟 .(i-1)天處于正常狀態，第i天處于買入狀態:這個可以，可以進行購買股票，買股票需要花錢，需要減去股票的錢pricesi
? ? 🌟 .(i-1)天處于正常狀態，第i天處于冷凍期狀態:這個不可以，冷凍期是在股票賣了之后才進入的

下面有個簡圖描述上面信息

箭頭方向表示：從（i-1）天到第i天

3.初始化+邊界條件

本題初始化比較簡單，不需要創建虛擬節點了
dp[0][0]=-prices[0]；這一天只買了股票，買是需要花錢的
dp[0][1]=0;買了有緊接著賣了，沒有利潤
dp[0][2]=0;

4.填表順序

從左往右

5.返回值是什么

最后一天的最大收益有兩種可能，而且一定是“不持有”狀態下的兩種可能，把這兩種“不持有”比較一下大小，返回即可
max(dp[n-1][1],dp[n–1][2]);

三、代碼實現

class Solution {
public:int maxProfit(vector<int>& prices) {//建表int n=prices.size();if(n==0){return 0;}vector<vector<int>>dp (n,vector<int>(3));//初始化dp[0][0]=-prices[0];dp[0][1]=0;dp[0][2]=0;//填表for(int i=1;i<n;i++){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][2],dp[i-1][1]);}//返回值return max(dp[n-1][1],dp[n-1][2]);}
};

總結

以上就是我們對本題詳細介紹，希望對大家的學習有所幫助，僅供參考 如有錯誤請大佬指點我會盡快去改正 歡迎大家來評論~~😘😘😘😘