买卖股票的最佳时机 III

题目描述：

提示：

• 1 <= prices.length <= 105
• 0 <= prices[i] <= 105

分析过程：

写动态规划，我们需要考虑一下问题：

1. 定义状态
2. 状态转移方程
3. 初始条件
4.  遍历顺序

4种状态：

实现先思考一共有几种状态，题目当中说我们一共最多可以买卖两次股票，所以买卖股票一共有四种情况，加上不持有股票，就是以下4种状态：

1. 第一个持有股票
2. 第一次卖出股票
3. 第二次持有股票
4. 第二次卖出股票

 转移方程：

第一次买入：
        在第 i 天，可以选择在第 i 天买入，或者保持之前的买入状态。
buy1[i] = max(buy1[i-1], -prices[i])
（初始资金为 0，第一次买入后的余额是 -prices[i]）
第一次卖出：
        在第 i 天，可以选择在第 i 天卖出，或者保持之前的卖出状态。
sell1[i] = max(sell1[i-1], buy1[i-1] + prices[i])
第二次买入：
        在第 i 天，可以选择在第 i 天买入（用第一次卖出的利润），或者保持之前的买入状态。
buy2[i] = max(buy2[i-1], sell1[i-1] - prices[i])
第二次卖出：
        在第 i 天，可以选择在第 i 天卖出，或者保持之前的卖出状态。
sell2[i] = max(sell2[i-1], buy2[i-1] + prices[i])

 遍历顺序:

通过上面的转移方程，我们可以看出，我们只需要一次遍历，就可以得出我们的dp 

初始化： 

buy1[0] = -prices[0]（第一天买入）
sell1[0] = 0（第一天无法卖出）
buy2[0] = -prices[0]（允许同一天买入两次？其实此时第一次卖出利润为 0，所以 buy2[0] = 0 - prices[0]）
sell2[0] = 0（第一天无法卖出两次）  

 代码：

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

买卖股票的最佳时机 IV

题目描述：

• 1 <= k <= 100
• 1 <= prices.length <= 1000
• 0 <= prices[i] <= 1000

从题目当中我们可以看出，这道题多了一个限制，就是我们只能最多买k张股票

分析过程：

最多买2张股票和最多买k张股票的区别是哪里呢，买两张股票是4个状态，那买k张股票不是2k个状态吗，事实上就是这样，我们只需要在里面套上一层for循环就可以了，具体实现的逻辑和上面的一样

代码：

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        int n = prices.size();
        
        // 边界情况：如果没有股票或者价格为空，直接返回 0
        if (n == 0) return 0;
        
        // 如果k大于等于n/2，意味着可以进行无限次交易，用贪心算法来处理
        if (k >= n / 2) {
            int profit = 0;
            for (int i = 1; i < n; ++i) {
                if (prices[i] > prices[i - 1]) {
                    profit += prices[i] - prices[i - 1];
                }
            }
            return profit;
        }
        
        // dp[i][j] 表示在第i天进行至多j次交易的最大利润
        vector<vector<int>> dp(n, vector<int>(k + 1, 0));
        
        // 进行每次交易
        for (int j = 1; j <= k; ++j) {
            int maxDiff = -prices[0];  // maxDiff 表示买入股票后的最大利润
            for (int i = 1; i < n; ++i) {
                dp[i][j] = max(dp[i - 1][j], prices[i] + maxDiff);  // 不交易或者卖出股票
                maxDiff = max(maxDiff, dp[i][j - 1] - prices[i]);  // 更新最大买入利润
            }
        }
        
        return dp[n - 1][k];  // 返回最终最大利润
    }
};