leetcode 121. 买卖股票的最佳时机-Toy模板网

这篇具有很好参考价值的文章主要介绍了leetcode 121. 买卖股票的最佳时机。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

2023.8.20

leetcode 121. 买卖股票的最佳时机,leetcode专栏,leetcode,算法,职场和发展,数据结构,cpp

本题用dp算法做，dp[i]的含义：前 i+1天能获得的最大利润。然后每次循环时需要维护一个最小值min_num ：即 i+1天中股票的最低价。剩下的步骤都很常规，代码如下：

一维dp：

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

二维dp：

dp[i][0]:第i天持有股票所拥有的最多现金。

dp[i][1]:第i天不持有股票所拥有的最多现金。

持有股票：可能之前就持有了股票，也可能是今天刚买的。即：dp[i][0] = max(dp[i-1][0] , -prices[i]);

不持有股票：可能之前就没持有，也可能是今天刚卖出。即：dp[i][1] = max(dp[i-1][1] , dp[i-1][0]+prices[i]);

代码如下：

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

2023.10.22

二刷。动态规划，一维和二维dp数组的java代码如下：

一维dp：

class Solution {
    public int maxProfit(int[] prices) {
        int[] dp = new int[prices.length];
        dp[0] = 0;
        int min_price = prices[0];
        for(int i=1; i<prices.length; i++){
            dp[i] = Math.max(dp[i-1] , prices[i]-min_price);
            min_price = Math.min(min_price , prices[i]);
        }
        return dp[prices.length-1];
    }
}

二维dp：

class Solution {
    public int maxProfit(int[] prices) {
        int[][] dp = new int[prices.length][2];
        dp[0][0] = -prices[0];
        dp[0][1] = 0;
        for(int i=1; i<prices.length; i++){
            //持股
            dp[i][0] = Math.max(dp[i-1][0] , -prices[i]);
            //不持股
            dp[i][1] = Math.max(dp[i-1][1] , dp[i-1][0]+prices[i]);
        }
        return dp[prices.length-1][1];
    }
}

ps:在持股的情况下，如果是刚买进股票，此时现金是 -prices[i] ，为什么？因为本题股票只会买入一次(后面的股票问题会有买入多次的情况)，所以当前的初始现金肯定是0，即0-price[i] = -price[i]文章来源地址https://www.toymoban.com/news/detail-660237.html

到了这里，关于leetcode 121. 买卖股票的最佳时机的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！