122.best-time-to-buy-and-sell-stock-ii 买卖股票的最佳时机II

问题描述

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

解题思路

本题的关键是要找dp的递推关系，分两种情况讨论:

• prices[i - 1]不会被选择，那么dp[i] = dp[i - 1]，其实也说明，prices[i - 1] < prices[i - 2]；
• prices[i - 1]被选择，那么prices[i - 1] >= prices[i - 2]，dp[i] = dp[i - 1] + prices[i - 1] - prices[i - 2]。

代码

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