思路

這道題目可以說是動態規劃：123.買賣股票的最佳時機III的進階版，這里要求至多有k次交易。

確定dp數組以及下標的含義

在動態規劃：123.買賣股票的最佳時機III中，我是定義了一個二維dp數組，本題其實依然可以用一個二維dp數組。

使用二維數組 dp[i][j] ：第i天的狀態為j，所剩下的最大現金是dp[i][j]

j的狀態表示為：

• 0 表示不操作
• 1 第一次買入
• 2 第一次賣出
• 3 第二次買入
• 4 第二次賣出
• …

大家應該發現規律了吧 ，除了0以外，偶數就是賣出，奇數就是買入。

題目要求是至多有K筆交易，那么j的范圍就定義為 2 * k + 1 就可以了。

所以二維dp數組的C++定義為：

vector<vector<int>> dp(prices.size(), vector<int>(2 * k + 1, 0));

確定遞推公式

還要強調一下：dp[i][1]，表示的是第i天，買入股票的狀態，并不是說一定要第i天買入股票，這是很多同學容易陷入的誤區。

達到dp[i][1]狀態，有兩個具體操作：

• 操作一：第i天買入股票了，那么dp[i][1] = dp[i - 1][0] - prices[i]
• 操作二：第i天沒有操作，而是沿用前一天買入的狀態，即：dp[i][1] = dp[i - 1][1]

選最大的，所以 dp[i][1] = max(dp[i - 1][0] - prices[i], dp[i - 1][0]);

同理dp[i][2]也有兩個操作：

• 操作一：第i天賣出股票了，那么dp[i][2] = dp[i - 1][1] + prices[i]
• 操作二：第i天沒有操作，沿用前一天賣出股票的狀態，即：dp[i][2] = dp[i - 1][2]

所以dp[i][2] = max(dp[i - 1][i] + prices[i], dp[i][2])

同理可以類比剩下的狀態，代碼如下：

for (int j = 0; j < 2 * k - 1; j += 2) {dp[i][j + 1] = max(dp[i - 1][j + 1], dp[i - 1][j] - prices[i]);dp[i][j + 2] = max(dp[i - 1][j + 2], dp[i - 1][j + 1] + prices[i]); }

本題和動態規劃：123.買賣股票的最佳時機III最大的區別就是這里要類比j為奇數是買，偶數是賣剩的狀態。

dp數組如何初始化

第0天沒有操作，這個最容易想到，就是0，即：dp[0][0] = 0;

第0天做第一次買入的操作，dp[0][1] = -prices[0];

第0天做第一次賣出的操作，這個初始值應該是多少呢？

首先賣出的操作一定是收獲利潤，整個股票買賣最差情況也就是沒有盈利即全程無操作現金為0，

從遞推公式中可以看出每次是取最大值，那么既然是收獲利潤如果比0還小了就沒有必要收獲這個利潤了。

所以dp[0][2] = 0;

第0天第二次買入操作，初始值應該是多少呢？

不用管第幾次，現在手頭上沒有現金，只要買入，現金就做相應的減少。

第二次買入操作，初始化為：dp[0][3] = -prices[0];

所以同理可以推出dp[0][j]當j為奇數的時候都初始化為 -prices[0]

代碼如下：

for (int j = 1; j < 2 * k; j += 2) {dp[0][j] = -prices[0]; }

在初始化的地方同樣要類比j為偶數是賣、奇數是買的狀態。

確定遍歷順序

從遞歸公式其實已經可以看出，一定是從前向后遍歷，因為dp[i]，依靠dp[i - 1]的數值。

舉例推導dp數組

以輸入[1,2,3,4,5]，k=2為例。

最后一次賣出，一定是利潤最大的，dp[prices.size() - 1][2 * k]即紅色部分就是最后求解。

以上分析完畢，C++代碼如下：

class Solution { public:int maxProfit(int k, vector<int>& prices) {if(prices.size()==0) return 0;vector<vector<int>> dp(prices.size(),vector<int>(2*k+1,0));for(int ii=1;ii<2*k;ii+=2){//dp[0][ii]=-prices[0];}for(int ii=1;ii<prices.size();ii++){for(int jj=0;jj<2*k;jj+=2){//dp[ii][jj+1]=max(dp[ii-1][jj]-prices[ii],dp[ii-1][jj+1]);dp[ii][jj+2]=max(dp[ii-1][jj+1]+prices[ii],dp[ii-1][jj+2]);}}return dp[prices.size()-1][2*k];} };

總結

以上是生活随笔為你收集整理的买卖股票的最佳时机IV的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。