動態規劃10

動態規劃5步曲，個人感覺應該加一步狀態分析

狀態分析：

1. 列出所有的狀態，將狀態歸納后定義dp數組
2. 狀態轉移，狀態怎么轉移也就是遞推公式是什么

買賣股票的動規五部曲分析如下：

1 確定dp數組（dp table）以及下標的含義

列出所有的狀態：

1. 持有 持有狀態包含兩種情況，繼續持有和當天買入
2. 不持有 不持有包含兩種狀態，當天賣出和維持前一天的未持有狀態

dp[i][0] 表示當天持有或者當天買入的的最大值
dp[i][1] 表示當天不持有的最大值

確定遞推公式

繼續持有就是 dp[i-1][0] 上一天的持有的值
當天買入就是前一天的沒有買入的值減去當天股票的價值
可以得出，當天持有
dp[i][0] = max(dp[i - 1][0], -prices[i]);

dp[i][1] 表示當天不持有的最大值
就是保持前一天的未持有狀態和當天賣出的狀態的最大值
dp[i][1] = max(dp[i - 1][1], + prices[i]);

dp數組如何初始化

由遞推公式 dp[i][0] = max(dp[i - 1][0], -prices[i]); 和 dp[i][1] = max(dp[i - 1][1], prices[i] + dp[i - 1][0]);可以看出

其基礎都是要從dp[0][0]和dp[0][1]推導出來。

那么dp[0][0]表示第0天持有股票，此時的持有股票就一定是買入股票了，因為不可能有前一天推出來，所以dp[0][0] -= prices[0];

dp[0][1]表示第0天不持有股票，不持有股票那么現金就是0，所以dp[0][1] = 0;

最大值一定是最后一次賣出的價格

121. 買賣股票的最佳時機

leetcode題目鏈接
視頻講解
文章講解

class Solution {
public:int maxProfit(vector<int>& prices) {vector<vector<int>> dp(prices.size(),vector<int>(2,0));//dp[i][0] 表示當天持有的最大價值//dp[i][1] 表示當天賣出后不持有的最大價值//初始化dp[0][0] = -prices[0];dp[0][1] = 0;for(int i = 1; i < prices.size(); i ++) {dp[i][0] = max(dp[i-1][0], 0 - prices[i]);//dp[i][0] = max(dp[i-1][0], dp[i-1][1] -prices[i]);//當天賣出一定是在前面買入的情況下賣出的，所以是dp[i-1][0] + prices[i]dp[i][1] = max(dp[i-1][1], dp[i-1][0] + prices[i]);}//最大值一定是最后一次賣出的價格return dp[prices.size() -1][1];}
};

122.買賣股票的最佳時機II

leetcode題目鏈接
視頻講解
文章講解

class Solution {
public:int maxProfit(vector<int>& prices) {vector<vector<int>> dp(prices.size(), vector<int>(2,0));dp[0][0] = -prices[0];dp[0][1] = 0;for(int i = 1; i < prices.size(); 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][0] + prices[i]);}return dp[prices.size()-1][1];}
};

動態規劃11

一天可以買賣多次很重要

123.買賣股票的最佳時機III

這道題一下子就難度上來了，關鍵在于至多買賣兩次，這意味著可以買賣一次，可以買賣兩次，也可以不買賣。
leetcode題目鏈接
視頻講解
文章講解

// 版本一
class Solution {
public:int maxProfit(vector<int>& prices) {if (prices.size() == 0) return 0;vector<vector<int>> dp(prices.size(), vector<int>(5, 0));dp[0][1] = -prices[0];dp[0][3] = -prices[0];for (int i = 1; i < prices.size(); i++) {dp[i][0] = dp[i - 1][0];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];}
};

188.買賣股票的最佳時機IV

本題是123.買賣股票的最佳時機III 的進階版
leetcode題目鏈接
視頻講解
文章講解

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 j = 1; j < 2 * k; j += 2) {dp[0][j] = -prices[0];}for (int i = 1;i < prices.size(); i++) {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]);}}return dp[prices.size() - 1][2 * k];}
};