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

2024-10-09 19:46:11

力扣 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);

    }

};

最新文章

热门文章