一：題目

二:上碼

class Solution { public:/**思路:1.動態規劃五步走1>:確定dp數組以及下標的含義因為題目給出至多完成兩筆交易 那么我們一天的狀態就有5種0 無操作1 第一次買入2 第一次賣出3 第二次買入4 第二次賣出dp[i][j] 表示的是在第i天 [0,4] 其中某個狀態下 已經所剩下的錢2>:確定dp數組遞推公式dp[i][1] 表示的是第i天,買入股票的狀態;那么這個狀態我們可以是買入的狀態；也可以是不買入沿用上一天的狀態;- 買入股票的話 那么就證明我們以后還得賣出 所以就是用我們剩下的錢減去它:dp[i][1] = dp[i-1][0] - prices[i];//因為我們不能連續操作所以我們上一天狀態的是無操作- 不買入股票的話 那么我們就可以知道的是 我們就是昨天的狀態 dp[i][1] = dp[i-1][1];- 那么我們dp[i][1]到底該如何取值呢?當然是取最大值dp[i][1] = max(dp[i-1][0] - prices[i],dp[i-1][1]);dp[i][2] 表示的是第i天 賣出股票的狀態 我們可以選擇賣出 當然也可以選著沒有操作 - 賣出股票了 那就證明我們掙錢了 就是在今天 我們可以經prices[i]收入囊中dp[i][2] = dp[i-1][1] + prices[i];//這里的dp[i-1][1] 這里的j=1 是因為 我們可能前一天買入了//當然也有可能 前一天也沿用更前一天的狀態; 但是j != 2//因為連續兩天不能都是賣出的狀態- 沒賣出 有可能 后幾天比今天的價格更高 dp[i][2] = dp[i-1][2]；//每賣出的話 我們的狀態就可以和前面的狀態一樣 因為我們并不是連續操作的dp[i][2] = max(dp[i-1][1]+prices[i],dp[i-1][2]);同理我們可以得出:dp[i][3] = max(dp[i-1][2] - prices[i],dp[i-1][3]);dp[i][4] = max(dp[i-1][3] - prices[i],dp[i-1][4]);3>:確定dp數組的初始化初始化也就是在第0天的操作dp[0][0] = 0;dp[0][1] = -prices[i];//因為目前手里還沒錢 所以我們賣出的話肯定是負數dp[0][2] = 0; //首先賣出的話我們肯定是賺錢的 因為我們還獲取不到前一天的狀態 所以 dp[0][2] = 0dp[0][3] = -prices[i];dp[0][4] = 0;4>:確定dp數組的遍歷順序dp[i]依賴于昨天的狀態 所以是正序5>:舉例驗證**/int maxProfit(vector<int>& prices) {vector<vector<int> > dp(prices.size(),vector<int>(5,0)); //dp(行,列)dp[0][1] = -prices[0];dp[0][3] = -prices[0];for (int i = 1; i < prices.size(); i++) {//天數// = max(買入,沒操作)// = max(賣出,沒操作) dp[i][1] = max(dp[i-1][0] - prices[i],dp[i-1][1]);dp[i][2] = max(dp[i-1][1] + prices[i],dp[i-1][2]);dp[i][3] = max(dp[i-1][2] - prices[i],dp[i-1][3]);dp[i][4] = max(dp[i-1][3] + prices[i],dp[i-1][4]);}return dp[prices.size()-1][4];} };

慢慢來吧 慢慢進步吧 ！ 冰凍三尺非一日之寒

總結

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

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