LeetCode-122 买卖股票的最佳时机 II

题目描述

来源：力扣（LeetCode）链接：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii

给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。

在每一天，你可以决定是否购买和/或出售股票。你在任何时候最多只能持有一股股票。你也可以先购买，然后在同一天出售。

返回你能获得的最大利润

示例1:

输入：prices = [7,1,5,3,6,4]
输出：7
解释：在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 
     随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3 
     总利润为 4 + 3 = 7 

题解

动态规划

假设用 $dp[i]$ 来记录每天交易结束后的最大利润

每天的交易结束后，会有两种状态

手里仍持有股票的最大利润 $dp[i][0]$
手里未持有股票的最大利润 $dp[i][1]$

用 $dp[i-1][0], dp[i-1][1]$ 来表示前一天手里持有股票的状态对应的最大利润

当今天手里持有股票时，可能的状态转移为前一天持有股票，即 $dp[i-1][1]$ ，或者前一天未持有股票，这时需要花费股票的价格将其买入，即为 $dp[i-1][0]-prices[i]$ ，那么状态转移方程为

dp[i][1] = max\{dp[i-1][1], dp[i-1][0] - prices[i] \}

当今天手里未持有股票，可能的状态转移为前一天就未持有股票，即为 $dp[i-1][0]$ ，或是前一天持有股票，今天进行了卖出，那么就加上今天股票的价格作为收益，即为 $dp[i-1][1] + prices[i]$ ，那么状态转移方程为

dp[i][0] = max\{dp[i-1][0], dp[i-1][1] + prices[i] \}

第一天时为初始状态，收益为 0 ， $dp[0][0]=0$ ，购入股票需要花费 $dp[0][1]=−prices[0]$
依次计算 $dp[i][0], dp[i][1]$ 即可，最后一天卖出股票的收益一定大于持有股票的收益，最终答案为 $dp[n-1][0]$

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

        return dp[n-1][0];
    }
};

Name	Value
时间复杂度	$O(n)$
空间复杂度	$O(n)$

用一个表格方便理解

input: prices = [7,1,5,3,6,4]

output: 7

i	0	1	2	3	4	5
prices	7	1	5	3	6	4
dp[i][0]	0	0 (0, -6)	4 (0, 4)	4 (4, 2)	7 (4, 7)	7 (7, 5)
dp[i][1]	-7	-1 (-7, -1)	-1 (-1, -5)	1 (-1, 1)	1 (1, -5)	3 (1, 3)

优化动态规划

其实每一天的状态只与前一天的状态相关，而与更早的状态无关，所有不需要维护更早的状态，可以将维护状态的数组优化为两个变量 $dp\_0=0, dp\_1 = -prices[0]$

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int dp_0 = 0;
        int dp_1 = -prices[0];
        for(int i = 1; i < prices.size(); ++i) {
            int new_dp_0 = max(dp_0, dp_1 + prices[i]);
            int new_dp_1= max(dp_1, dp_0 - prices[i]);
            dp_0 = new_dp_0;
            dp_1 = new_dp_1;
        }

        return dp_0;
    }
};

Name	Value
时间复杂度	$O(n)$
空间复杂度	$O(1)$

题目描述​

题解​

动态规划​

优化动态规划​

贪心​

题目描述

题解

动态规划

优化动态规划

贪心