当前位置:网站首页>力扣 122 买卖股票的最佳时机II

力扣 122 买卖股票的最佳时机II

2020-11-10 15:38:12 又啦

力扣 122 买卖股票的最佳时机II

思路:

  • 动态规划,表面上是\(O(2^n)\)的搜索空间,实际上该天的选择只与前一天的状态(是否持有股票)有关。从收益的角度来看,确实每一天的不同选择都会产生不同的分支。动态规划相当于对原解空间进行了剪枝,剪枝的关键在于之后的选择只与当前是否持有股票的状态有关,因此只需要保留当前状态下的最优值,就能保证最优解的保留。

  • 对于这种时间序列或者类似的问题,可重点考虑其每一个阶段的状态。若考虑卖出,买入和保持,就很复杂,但是考虑是否持有就变成只有两个状态了。

  • 本质上很像贪心,都能保证每一步的最优解。关键在于找到这个结构。

    \(dp[i][0] = max(dp[i-1][0],dp[i-1][1]+prices[i])\)

    \(dp[i][1] = max(dp[i-1][0] - prices[i],dp[i-1][1])\)

class Solution {
public:
    //动态规划
    int maxProfit(vector<int>& prices) {
        if(!prices.size()) return 0;
        int n = prices.size();
        int dp0 = 0;
        int dp1 = -prices[0];
        for(int i = 1; i < n; ++i){
            dp0 = max(dp0,dp1 + prices[i]);
            dp1 = max(dp0 - prices[i], dp1);
        }
        return max(dp0,dp1);
    }
};

版权声明
本文为[又啦]所创,转载请带上原文链接,感谢
https://www.cnblogs.com/jinjin-2018/p/13954080.html