代码随想录day41dp8

121. 买卖股票的最佳时机

题目链接
文章讲解
贪心

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int ans=0;
        int pre=prices[0];
        for(int i=1;i<prices.size();i++)
        {
            if(prices[i]-pre>0)
            {
                ans=max(prices[i]-pre,ans);
                continue;
            }
            pre=prices[i];
        }
        return ans;
    }
};

dp

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        if (n == 0) return 0;

        // dp[i][0] 表示第i天不持有股票的最大收益
        // dp[i][1] 表示第i天持有股票的最大收益
        vector<vector<int>> dp(n, vector<int>(2, 0));
        
        // 初始化
        dp[0][0] = 0;            // 第0天不持股
        dp[0][1] = -prices[0];   // 第0天持股，买入价格为-prices[0]

        for (int i = 1; i < n; ++i) {
            // 第i天不持股，要么昨天就不持股，要么今天卖掉
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
            // 第i天持股，要么昨天就持股，要么今天买入（只能买一次）
            dp[i][1] = max(dp[i - 1][1], -prices[i]);
        }

        // 最终答案为最后一天不持股时的最大收益
        return dp[n - 1][0];
    }
};

122.买卖股票的最佳时机II

题目链接
文章讲解
贪心

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int res = 0;  // 初始化最大利润为0

        // 遍历价格数组，计算每次相邻价格的利润
        for (int i = 0; i < prices.size() - 1; i++) {
            // 如果明天的价格比今天高，则进行买卖
            // prices[i+1] - prices[i] 为利润，如果为负数，则不进行交易（利润为0）
            res += max(prices[i + 1] - prices[i], 0);  
        }

        return res;  // 返回总利润
    }
};

dp

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        if (n == 0) return 0;

        // dp[i][0] - 第i天不持有股票的最大利润
        // dp[i][1] - 第i天持有股票的最大利润
        vector<vector<int>> dp(n, vector<int>(2, 0));
        
        // 初始状态
        dp[0][0] = 0;  // 第0天不持股
        dp[0][1] = -prices[0];  // 第0天持股，买入股票
        
        for (int i = 1; i < n; ++i) {
            // 第i天不持股，要么昨天就不持股，要么今天卖掉
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
            // 第i天持股，要么昨天就持股，要么今天买入
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
        }

        // 最终结果是第n-1天不持股的最大利润
        return dp[n - 1][0];
    }
};

123.买卖股票的最佳时机III

题目链接
文章讲解

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if (prices.size() == 0) return 0;  // 如果价格数组为空，返回 0 利润
        
        vector<vector<int>> dp(prices.size(), vector<int>(5, 0));  // 创建 DP 数组
        
        // 初始化第 0 天的交易状态
        dp[0][1] = -prices[0];  // 第 0 天持有第一笔股票，最大利润是 -prices[0]
        dp[0][3] = -prices[0];  // 第 0 天持有第二笔股票，最大利润是 -prices[0]

        // 从第 1 天开始遍历
        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];
    }
};