算法训练第五十天-Toy模板网

这篇具有很好参考价值的文章主要介绍了算法训练第五十天。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

总结：今日是股票问题的变式，关键是要把握搞清楚dp数组的含义，自己也是被搞混了很久

188. 买卖股票的最佳时机 IV - 力扣（LeetCode）

代码：

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        if(prices.size() == 1)
        return 0;
        int n = prices.size();
        vector<vector<int>> dp(n + 1,vector<int>(2 * k,0));
        for(int i = 0;i < 2 * k;i = i + 2)
        {
            dp[1][i] = -prices[0];//持有
            dp[1][i + 1] = 0;//不持有
        }

        for(int i = 2;i <= n;i++)
        {
            for(int j = 0;j < 2 * k;j = j + 2)
            {
                if(j == 0)
                dp[i][j] = max(dp[i - 1][j],-prices[i - 1]);
                else
                dp[i][j] = max(dp[i - 1][j],dp[i - 1][j - 1]-prices[i - 1]);
                dp[i][j + 1] = max(dp[i - 1][j + 1],dp[i - 1][j] + prices[i - 1]);
            }
        }
        return dp[prices.size()][2 * k - 1];
    }
};

123. 买卖股票的最佳时机 III - 力扣（LeetCode）文章来源地址https://www.toymoban.com/news/detail-684955.html

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if(prices.size() == 1 || prices.size() == 0)
        return 0;
        int n = prices.size();
        vector<vector<int>> dp(prices.size() + 1,vector<int>(4,0));
        dp[1][0] = -prices[0];
        dp[1][1] = 0;
        dp[1][2] = -prices[0];
        dp[1][3] = 0;

        for(int i = 2;i <= prices.size();i++)
        {
            dp[i][0] = max(dp[i - 1][0],-prices[i - 1]);
            dp[i][1] = max(dp[i - 1][1],dp[i - 1][0] + prices[i - 1]);
            dp[i][2] = max(dp[i - 1][2],dp[i - 1][1] - prices[i - 1]);
            dp[i][3] = max(dp[i - 1][3],dp[i - 1][2] + prices[i - 1]);
        }
        return max(max(dp[n][0],dp[n][1]),max(dp[n][2],dp[n][3]));
    }
};

到了这里，关于算法训练第五十天的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！