Leetcode股票問題總結(jié)篇

• 動(dòng)態(tài)規(guī)劃的股票問題一共六道題，買賣股票最佳時(shí)機(jī)和買賣股票手續(xù)費(fèi)都是一個(gè)類型的問題，維護(hù)好買入和賣出兩個(gè)狀態(tài)即可，方法一摸一樣。而冷凍期也差不多就是狀態(tài)多了點(diǎn)，買入、保持賣出、當(dāng)日賣出、以及冷凍期四個(gè)狀態(tài)。
• 做題方法還是動(dòng)態(tài)規(guī)劃五部曲：
  • 明確dp數(shù)組含義，這里六道題全部第i天都是手里買入狀態(tài)或者賣出狀態(tài)的現(xiàn)金數(shù)是多少，這篇文章下標(biāo)0代表未持有，下標(biāo)1代表持有。
  • 寫出遞推公式，下面寫了最基本的，其他題的公式都是在這個(gè)基礎(chǔ)上做了修改的：

    	dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i]);dp[i][1] = max(dp[i - 1][1], -prices[i]);
    

    • 最佳時(shí)機(jī)2那道題就是在這個(gè)基礎(chǔ)上，修改買入時(shí)的遞推公式為dp[i][1] = max(dp[i - 1][1], dp[i - 1][0]-prices[i - 1]);
    • 最佳時(shí)機(jī)3那道題是增加兩個(gè)狀態(tài)表示第二次買入和賣出：

          dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]);dp[i][2] = max(dp[i - 1][2], dp[i - 1][1] + prices[i]);dp[i][3] = max(dp[i - 1][3], dp[i - 1][2] - prices[i]);dp[i][4] = max(dp[i - 1][4], dp[i - 1][3] + prices[i]);
      

    • 最佳時(shí)機(jī)4那道題是增加到2 * k個(gè)狀態(tài)，那么內(nèi)層就要變?yōu)殡p層循環(huán)為各個(gè)狀態(tài)賦值了。

          dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1] - prices[i]);dp[i][j + 1] = max(dp[i - 1][j + 1], dp[i - 1][j] + prices[i]);
      

    • 凍結(jié)期那道題的遞推公式就稍微復(fù)雜了，需要維護(hù)四個(gè)狀態(tài)，分別是買入、保持賣出、當(dāng)日賣出、以及冷凍期。

      	dp[i][0] = max(dp[i - 1][0], max(dp[i - 1][3], dp[i - 1][1]) - prices[i]);dp[i][1] = max(dp[i - 1][1], dp[i - 1][3]);dp[i][2] = dp[i - 1][0] + prices[i];dp[i][3] = dp[i - 1][2];
      

    • 含手續(xù)費(fèi)這道題和第二道題一摸一樣，在賣出時(shí)減去手續(xù)費(fèi)就行。
  • 初始化：每次買入的時(shí)候必須初始化為-price[0]，其他賦值為0即可。
  • 遍歷順序：由于需要用到 i - 1的資金，所以從前往后遍歷

121. 買賣股票的最佳時(shí)機(jī)

力扣題目鏈接

代碼實(shí)現(xiàn)：

int maxProfit(vector<int>& prices) {vector<vector<int>> dp(prices.size() + 1, vector(2, 0));dp[1][0] = 0, dp[1][1] = -prices[0];//二維數(shù)組0代表不持有，1代表持有for (int i = 2; i <= prices.size(); ++i) {dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i - 1]);dp[i][1] = max(dp[i - 1][1], -prices[i - 1]);}return dp[prices.size()][0];}

• 動(dòng)態(tài)規(guī)劃二維數(shù)組滾動(dòng)數(shù)組優(yōu)化方式：

int maxProfit(vector<int>& prices) {vector<vector<int>> dp(2, vector(2, 0));//只記錄當(dāng)前天和前一天的狀態(tài)即可dp[0][0] = 0, dp[0][1] = -prices[0];//二維數(shù)組0代表不持有，1代表持有for (int i = 1; i < prices.size(); ++i) {dp[i % 2][0] = max(dp[(i - 1) % 2][0], dp[(i - 1) % 2][1] + prices[i]);dp[i % 2][1] = max(dp[(i - 1) % 2][1], -prices[i]);//看實(shí)現(xiàn)通過求余，每次取的都是前一個(gè)元素值}return dp[(prices.size() + 1) % 2][0];//用+1，因?yàn)閿?shù)組可能為空}

• 動(dòng)態(tài)規(guī)劃一維數(shù)組實(shí)現(xiàn)法，比二維實(shí)現(xiàn)更簡潔

int maxProfit(vector<int>& prices) {vector<int> dp(2, 0);//只記錄當(dāng)前天的狀態(tài)即可dp[0] = 0, dp[1] = -prices[0];//0代表不持有，1代表持有for (int i = 1; i < prices.size(); ++i) {dp[0] = max(dp[0], dp[1] + prices[i]);dp[1] = max(dp[1], -prices[i]);}return dp[0];}

• 貪心法實(shí)現(xiàn)（每次更新左邊界為最小值，然后不斷更新result結(jié)果）：

int maxProfit(vector<int>& prices) {int low = INT_MAX, result = 0;for (int i = 0; i < prices.size(); ++i) {low = min(low, prices[i]);result = max(result, prices[i] - low);}return result;}

買賣股票的最佳時(shí)機(jī)2

力扣題目鏈接
思路：

• 在上題基礎(chǔ)上增加了買賣次數(shù)，修改買入時(shí)的計(jì)算方法即可。

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

• 普通動(dòng)態(tài)規(guī)劃想法，直接計(jì)算每天的利潤（和貪心類似）

int maxProfit(vector<int>& prices) {//dp[i] = max(dp[i - 1], dp[i - 1] + prices[i] - prices[i - 1]);vector<int> dp(prices.size(), 0);for (int i = 1; i < prices.size(); ++i) {dp[i] = max(dp[i - 1], dp[i - 1] + prices[i] - prices[i - 1]);}   return dp[prices.size() - 1];}

• 用雙狀態(tài)實(shí)現(xiàn)的方法（這里用一維數(shù)組實(shí)現(xiàn)的，也可以是二維）

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

• 貪心法

int maxProfit(vector<int>& prices) {int profit = 0;for (int i = 1; i < prices.size(); i++) {profit += max(prices[i] - prices[i - 1], 0);}return profit;}

• 雙指針法

int maxProfit(vector<int>& prices) {int profit = 0, buy_index = 0;for (int i = 0; i < prices.size() - 1; i++) {if (prices[i] > prices[i + 1]) {profit += prices[i] - prices[buy_index];buy_index = i + 1;continue;}if (i + 1 == prices.size() - 1) {profit += prices[i + 1] - prices[buy_index];}}return profit;}

買賣股票的最佳時(shí)機(jī)3

力扣題目鏈接
思路：

• 這道題規(guī)定只能買賣兩次，實(shí)現(xiàn)方法上面已經(jīng)寫過了，直接上代碼

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

int maxProfit(vector<int>& prices) {vector<vector<int>> dp(prices.size(), vector<int>(5, 0));dp[0][1] = -prices[0], dp[0][3] = -prices[0];//相當(dāng)于當(dāng)天買賣一次后再次買入for (int i = 1; i < prices.size(); ++i) {dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]);dp[i][2] = max(dp[i - 1][2], dp[i - 1][1] + prices[i]);dp[i][3] = max(dp[i - 1][3], dp[i - 1][2] - prices[i]);dp[i][4] = max(dp[i - 1][4], dp[i - 1][3] + prices[i]);}return dp[prices.size() - 1][4];}

買賣股票的最佳時(shí)機(jī)4

力扣題目鏈接

思路：
買賣次數(shù)規(guī)定為k次，需要利用循環(huán)給每次買賣賦值。

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

int maxProfit(int k, vector<int>& prices) {vector<vector<int>> dp(prices.size(), vector<int>(k * 2 + 1, 0));for (int i = 1; i < 2 * k + 1; i += 2) {dp[0][i] = -prices[0];}for (int i = 1; i < prices.size(); ++i) {for (int j = 1; j <= 2 * k - 1; j += 2) {dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1] - prices[i]);dp[i][j + 1] = max(dp[i - 1][j + 1], dp[i - 1][j] + prices[i]);}}return dp[prices.size() - 1][2 * k];}

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

力扣題目鏈接
題目描述：
在第二題基礎(chǔ)上，增加了冷凍期，需要維護(hù)四個(gè)狀態(tài)

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

int maxProfit(vector<int>& prices) {int len = prices.size();vector<vector<int>> dp(len, vector<int>(4, 0));dp[0][0] = -prices[0];for (int i = 1; i < len; ++i) {dp[i][0] = max(dp[i - 1][0], max(dp[i - 1][3], dp[i - 1][1]) - prices[i]);dp[i][1] = max(dp[i - 1][1], dp[i - 1][3]);dp[i][2] = dp[i - 1][0] + prices[i];dp[i][3] = dp[i - 1][2];}return max(dp[len - 1][1], max(dp[len - 1][2], dp[len - 1][3]));}

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

力扣題目鏈接
題目描述：
和第二題基本一樣，賣出時(shí)減去手續(xù)費(fèi)就行了

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

int maxProfit(vector<int>& prices, int fee) {vector<vector<int>> dp(prices.size(), vector<int>(2, 0));dp[0][1] = -prices[0];for (int i = 1; i < prices.size(); ++i) {dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i] - fee);dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]);}return dp[prices.size() - 1][0];}