买卖股票最佳时机II

题目描述

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

示例 1：

输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

题目链接：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/

文章讲解：https://programmercarl.com/0122.买卖股票的最佳时机II（动态规划）.html

思路

这道题和 121. 买卖股票的最佳时机 (opens new window) 的区别在于可以买卖多次。

之前是用的贪心解法，把所有上升区间求出来，找出所有利润，对应贪心思维是只要当天相比于前一天价格高，就前一天买入当天卖出。

这次重点讲动规，dp数组含义和上次相同

动规五部曲

1、dp数组及下标含义

• dp[i][0]表示第i天持有股票所得现金。
• dp[i][1] 表示第i天不持有股票所得最多现金。
• 两者表述稍有不同，是因为持有股票的时候一定不会获得更多的利润，因此改为持有时所得先进/利润

2、递推公式

如果第 i 天持有股票对应两种情况：

• 第 i - 1 天就持有股票，此时dp[i][0] = dp[i-1][0]
• 第 i - 1 天买入股票，那么此时dp[i][0] = dp[i-1][1]-prices[i] -- 昨天不持有股票的所得现金减去 今天的股票价格

如果第 i 天不持有股票，对应两种情况：

• 第 i - 1 天不持有，保持现状 dp[i][1] = dp[i-1][1]
• 第 i - 1 天卖出股票，那就是第 i-1天不持有股票+今天股票价格 dp[i][1] = dp[i - 1][0] + prices[i]

3、dp数组初始化

初始化第一行即可，和上一题一样

4、确定遍历顺序

正序

5、举例推导

以prices = 【7,1,5,3,6,4】;为例

dp数组如下：

第 1 天 -7 0 
第 2 天 -1 0 
第 3 天 -1 4 
第 4 天 1 4 
第 5 天 1 7 
第 6 天 3 7

代码实现

int maxProfit(vector<int>& prices) {
    vector<vector<int>> dp(prices.size(),vector<int>(2));
    dp[0][0] = -prices[0];// 第i天持有股票能获取的最大利润
    dp[0][1] = 0;
    for(int i = 1;i < prices.size();i++){
        dp[i][0] = max(dp[i - 1][0],dp[i - 1][1]-prices[i]);
        dp[i][1] = max(dp[i - 1][1],prices[i] + dp[i - 1][0]);
    }
    return dp[prices.size() - 1][1];
}