121. 买卖股票的最佳时机：一次买入卖出

1. 贪心算法

找最左边的最小值，和最右边的最大值，相减

class Solution {
public://贪心int maxProfit(vector<int>& prices) {int leftmin = INT_MAX;int result = 0;for(int i = 0; i < prices.size(); i++) {leftmin = min(leftmin, prices[i]);result = max(result, prices[i] - leftmin);}      return result;}
};

2. 动态规划

1. dp数组以及下标名义

dp[i][0] : 第i天，持有股票的最大收益, 可能之前买了不一定i天买

dp[i][1] : 第i天，不持有股票的最大收益，可能之前卖了不一定i天卖

2. 递归公式

如果第i天持有股票即dp[i][0]， 那么可以由两个状态推出来

1. 第i-1天就持有股票，那么就保持现状，所得现金就是昨天持有股票的所得现金 即：dp[i - 1][0]

2. 第i天买入股票，所得现金就是买入今天的股票后所得现金即：-prices[i]，现金本身为0，股票只买卖一次

3. 所以：dp[i][0] = max(dp[i - 1][0],-prices[i])
   如果第i天不持有股票即dp[i][1]， 那么可以由两个状态推出来

4. 第i-1天就不持有股票，那么就保持现状， 即：dp[i - 1][1]

5. 第i天卖出股票，所得现金就是卖出今天的股票后所得现金即：dp[i - 1][0] + prices[i]

6. 所以：dp[i][0] = max(dp[i - 1][0] + prices[i]， dp[i - 1][1])

3. dp数组如何初始化

dp[0][0] = -p[0]；
dp[0][1] = 0;

4. 代码

class Solution {
public://贪心int maxProfit(vector<int>& prices) {vector<vector<int>>dp(prices.size() + 1, vector<int>(2 , 0));dp[0][0] = - prices[0];for(int i = 1; i < prices.size(); i++) {dp[i][0] = max(dp[i - 1][0], - prices[i]); //第i天持有股票即dp[i][0]= 第i-1天就持有股票 or 第i天买入股票dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i]);//第i天不持有股票即dp[i][1] =第i-1天就不持有股票or第i天卖出股票}return max(dp[prices.size() - 1][0], dp[prices.size() - 1][1]);}
};

122. 买卖股票的最佳时机 II:可以多次买入卖出

2. 动态规划

1. dp数组以及下标名义

dp[i][0] : 第i天，持有股票的最大收益, 可能之前买了不一定i天买

dp[i][1] : 第i天，不持有股票的最大收益，可能之前卖了不一定i天卖

2. 递归公式

如果第i天持有股票即dp[i][0]， 那么可以由两个状态推出来

1. 第i-1天就持有股票，那么就保持现状，所得现金就是昨天持有股票的所得现金 即：dp[i - 1][0]

2. 第i天买入股票，所得现金就是买入今天的股票后所得现金即：-prices[i]，现金本身为0，股票只买卖一次

3. 所以：dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] -prices[i])和上一题不一样的地方
   如果第i天不持有股票即dp[i][1]， 那么可以由两个状态推出来

4. 第i-1天就不持有股票，那么就保持现状， 即：dp[i - 1][1]

5. 第i天卖出股票，所得现金就是卖出今天的股票后所得现金即：dp[i - 1][0] + prices[i]

6. 所以：dp[i][0] = max(dp[i - 1][0] + prices[i]， dp[i - 1][1])

3. dp数组如何初始化

dp[0][0] = -p[0]；
dp[0][1] = 0;

4. 代码

class Solution {
public://贪心int maxProfit(vector<int>& prices) {vector<vector<int>>dp(prices.size() + 1, vector<int>(2 , 0));dp[0][0] = - prices[0];for(int i = 1; i < prices.size(); i++) {dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]- prices[i]); //第i天持有股票即dp[i][0]= 第i-1天就持有股票 or 第i天买入股票dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i]);//第i天不持有股票即dp[i][1] =第i-1天就不持有股票or第i天卖出股票}return max(dp[prices.size() - 1][0], dp[prices.size() - 1][1]);}
};

123. 买卖股票的最佳时机 III：最多完成两笔交易

2. 动态规划

1. dp数组以及下标名义

一天一共就有五个状态，

0：没有操作 （其实我们也可以不设置这个状态）
1：第一次持有股票
2：第一次不持有股票
3：第二次持有股票
4：第二次不持有股票

2. 递归公式

情况一. dp[i][1]：

如果第i天第一次持有股票即dp[i][1]， 不是说第i天一定要买入股票，可能之前就买入了股票

1. 操作一：第i-1天没有操作：第一次持有股票：dp[i - 1][1]
2. 操作二：第i天买入股票，则第i-1天不持有股票：- prices[i]
3. 所以：dp[i][1] = max(dp[i - 1][1], - prices[i]）

情况二. dp[i][2]：

1. 操作一：第i天没有操作：延续前一天：dp[i - 1][2]
2. 操作二：第i天卖出股票，则：dp[i - 1][1] + prices[i]
3. dp[i][2] = max(dp[i - 1][1] + prices[i], dp[i - 1][2])

情况三. dp[i][3]：

1. 操作一：第i天没有操作：dp[i - 1][3]
2. 操作二：第i天买入股票，则：dp[i - 1][2] - prices[i]
3. dp[i][3] = max(dp[i - 1][2] - prices[i], dp[i - 1][3])

情况四. dp[i][4]：

4. 操作一：第i天没有操作：延续前一天：dp[i - 1][4]
5. 操作二：第i天卖出股票，则：dp[i - 1][3] + prices[i]
6. dp[i][4] = max(dp[i - 1][3] + prices[i], dp[i - 1][4])

3. dp数组如何初始化

dp[0][1] = -p[0]；
dp[0][3] = -p[0]；
第二次买入依赖于第一次卖出的状态，其实相当于第0天第一次买入了，第一次卖出了，然后再买入一次（第二次买入），那么现在手头上没有现金，只要买入，现金就做相应的减少。

4. 代码

class Solution {
public:int maxProfit(vector<int>& prices) {vector<vector<int>>dp(prices.size() + 1, vector<int>(5, 0));dp[0][1] = - prices[0];dp[0][3] = - prices[0];for(int i = 1; i < prices.size(); i++) {dp[i][1] = max(dp[i - 1][1], - prices[i]);dp[i][2] = max(dp[i - 1][1] + prices[i], dp[i - 1][2]);dp[i][3] = max(dp[i - 1][3], dp[i - 1][2] - prices[i]);dp[i][4] = max(dp[i - 1][3] + prices[i], dp[i - 1][4]);}int high1 = max(dp[prices.size() - 1][1], dp[prices.size() - 1][2]);int high2 = max(dp[prices.size() - 1][3], dp[prices.size() - 1][4]);return max(high1,high2);}
};

188. 买卖股票的最佳时机 IV:k次买入，k次卖出

2. 动态规划

1. dp数组以及下标名义

使用二维数组 dp[i][j] ：第i天的状态为j，所剩下的最大现金是dp[i][j]
j的状态表示为：

0 表示不操作
1 第一次买入
2 第一次卖出
3 第二次买入
4 第二次卖出
…

2. 递归公式

情况一. dp[i][1]：

如果第i天第一次持有股票即dp[i][1]， 不是说第i天一定要买入股票，可能之前就买入了股票

1. 操作一：第i-1天没有操作：第一次持有股票：dp[i - 1][1]
2. 操作二：第i天买入股票，则第i-1天不持有股票：- prices[i]
3. 所以：dp[i][1] = max( - prices[i]，dp[i - 1][1]）

情况二. dp[i][2]：

1. 操作一：第i天没有操作：延续前一天：dp[i - 1][2]
2. 操作二：第i天卖出股票，则：dp[i - 1][1] + prices[i]
3. dp[i][2] = max(dp[i - 1][1] + prices[i], dp[i - 1][2])

情况三. dp[i][3]：

1. 操作一：第i天没有操作：dp[i - 1][3]
2. 操作二：第i天买入股票，则：dp[i - 1][2] - prices[i]
3. dp[i][3] = max(dp[i - 1][2] - prices[i], dp[i - 1][3])
   …

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

3. dp数组如何初始化

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

4. 代码

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