. - 力扣（LeetCode）

121. 买卖股票的最佳时机

题目分析

动态规划的思路

在这个问题中，每一天都有两种状态：

返回结果

return dp[prices.size() - 1][1];

• 持有股票（对应于 dp[i][0]）
• 不持有股票（对应于 dp[i][1]）

• 对于每一天 i（从第二天开始计数，即 i=1）：

• 持股（dp[i][0]）的最大利润：如果前一天就持有股票，则继续持有的利润是 dp[i-1][0]；如果前一天不持股，那么今天买入股票的利润是 dp[i-1][1] - prices[i]。选择这两种情况中利润最大的一种。

  dp[i][0] = std::max(dp[i - 1][0], dp[i - 1][1] - prices[i]);

• 不持股（dp[i][1]）的最大利润：如果前一天就不持有股票，则继续不持有的利润是 dp[i-1][1]；如果前一天持有股票，那么今天卖出股票的利润是 dp[i-1][0] + prices[i]。选择这两种情况中利润最大的一种。

  dp[i][1] = std::max(dp[i - 1][1], dp[i - 1][0] + prices[i]);

acm模式代码

#include <vector>
#include <iostream>

class Solution {
public:
    int maxProfit(std::vector<int>& prices) {
        std::vector<std::vector<int>> dp(prices.size(), std::vector<int>(2, 0));
        dp[0][0] = -prices[0];
        dp[0][1] = 0;

        for (int i = 1; i < prices.size(); i++) {
            //持股
            dp[i][0] = std::max(dp[i - 1][0],  - prices[i]);
            //不持股
            dp[i][1] = std::max(dp[i - 1][1], dp[i - 1][0] + prices[i]);



        }
        return dp[prices.size() - 1][1];
    }
};

int main() {
    Solution sol;
    std::vector<int> prices = {7,1,5,3,6,4};
    int max = sol.maxProfit(prices);
    std::cout << "max:" << max << std::endl;
}

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

题目分析

在121. 买卖股票的最佳时机 (opens new window)中，因为股票全程只能买卖一次，所以如果买入股票，那么第i天持有股票即dp[i][0]一定就是 -prices[i]。

而本题，因为一只股票可以买卖多次，所以当第i天买入股票的时候，所持有的现金可能有之前买卖过的利润。

那么第i天持有股票即dp[i][0]，如果是第i天买入股票，所得现金就是昨天不持有股票的所得现金 减去 今天的股票价格 即：dp[i - 1][1] - prices[i]。

acm模式代码

#include <vector>
#include <iostream>

class Solution {
public:
    int maxProfit(std::vector<int>& prices) {
        std::vector<std::vector<int>> dp(prices.size(), std::vector<int>(2, 0));
        dp[0][0] = -prices[0];
        dp[0][1] = 0;

        for (int i = 1; i < prices.size(); i++) {
            //持股
            dp[i][0] = std::max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
            // dp[i][0] = std::max(dp[i - 1][0], - prices[i]);

            //不持股
            dp[i][1] = std::max(dp[i - 1][1], dp[i - 1][0] + prices[i]);

        }
        // for (auto i : dp) {
        //     for (int j = 0; j < dp[0].size(); j++) {
        //         std::cout << i[j] << " " ;
        //     }
        //     std::cout << std::endl;
        // }
        return dp[prices.size() - 1][1];
    }
};

int main() {
    Solution sol;
    std::vector<int> prices = {7,1,5,3,6,4};
    int max = sol.maxProfit(prices);
    std::cout << std::endl;
    std::cout << "max:" << max << std::endl;
}