121.買賣股票的最佳時機

（想寫動態規劃寫著寫著變成貪心了）

半貪心半動規：

int maxProfit(vector<int>& prices) {vector<int> dp(prices.size(), 0);int minVal = prices[0];for (int i = 1; i < prices.size(); ++i) {// 更新最低買入價格if (prices[i] < minVal) {minVal = prices[i];dp[i] = dp[i - 1];}// 嘗試賣出elsedp[i] = std::max(dp[i - 1], prices[i] - minVal);}return dp[prices.size() - 1];
}// 利用滾動數組的思路進行優化：
int maxProfit(vector<int>& prices) {int dp = 0;int minVal = prices[0];for (int i = 1; i < prices.size(); ++i) {if (prices[i] < minVal)minVal = prices[i];elsedp = std::max(dp, prices[i] - minVal);}return dp;
}

動規寫法，重點在于DP數組的定義

1、DP數組定義：

????????dp[i][j]為當前利潤，買入則減，賣出則加
????????· dp[i][0]表示如果當前持有股票，所能獲得的最大利潤（持有的股票可以是當天購入的也可以是之前購入的）
????????· dp[i][1]表示如果當前不持有股票，所能獲得的最大利潤（可以是還沒有購入過也可以是購入后賣出了）

2、DP數組初始化：dp[0]初始化為-prices[0]，起步資金為0，所以相當于第一次買入，即 dp[0] = 0 - prices[0]

3、遞推公式：

? ? ? ? · 對于dp[i][0]：判斷當日買入和前幾日買入，哪個更便宜，即：

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

? ? ? ? · 對于dp[i][1]：判斷當日賣出和前幾日賣出，哪個收益更高，即：

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

4、遍歷順序：按時間順序從前向后遍歷

int maxProfit(vector<int>& prices) {dp[0][0] = -prices[0];		// 購入第一支股票dp[0][1] = 0;for (int i = 1; i < prices.size(); ++i) {dp[i][0] = std::max(dp[i - 1][0], -prices[i]);// 賣出：前一天的最大賣出利潤 與 前一天持有+今日賣出所得 取較大值dp[i][1] = std::max(dp[i - 1][1], dp[i - 1][0] + prices[i]);}return dp[prices.size() - 1][1];
}

---

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

之前用貪心寫過這題

int maxProfit(vector<int>& prices) {vector<int> dp(prices.size(), 0);int curVal = prices[0];for (int i = 1; i < prices.size(); ++i) {if (prices[i] < curVal)dp[i] = dp[i - 1];elsedp[i] = dp[i - 1] + prices[i] - curVal;curVal = prices[i];}return dp[prices.size() - 1];
}// 用滾動數組思路進行寫法優化（完全變成了之前的貪心寫法）
int maxProfit(vector<int>& prices) {int dp = 0;int curVal = prices[0];for (int i = 1; i < prices.size(); ++i) {if (prices[i] > curVal)dp += prices[i] - curVal;curVal = prices[i];}return dp;
}

延續 買賣股票I 思路的動規寫法：

與 I 相比，差異在于可以反復買入賣出，即每次買入時的啟動資金不是0，而是之前賣出所得的資金總量

差異僅在于dp[i][0]的遞推公式：dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i])

int maxProfit(vector<int>& prices) {vector<vector<int>> dp(prices.size(), vector<int>(2, 0));dp[0][0] = -prices[0];for (int i = 1; i < prices.size(); ++i) {// 是否選擇今天買入dp[i][0] = std::max(dp[i - 1][0], dp[i - 1][1] - prices[i]);// 是否選擇今天賣出dp[i][1] = std::max(dp[i - 1][1], dp[i - 1][0] + prices[i]);}return dp[prices.size() - 1][1];
}