动态规划：leetcode 122 股票买卖最佳时机（可多次买卖）

本文利用动归五部曲解决股票买卖最佳时机（可多次买卖）以及背后的动态规划思想。

给定一个数组 prices ，其中 prices[i] 是一支给定股票第 \(i\) 天的价格。 设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例1：

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

示例2：

1输入: prices = [1,2,3,4,5]
2输出: 4
3解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
4注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。

分析：利用动归五部曲，

1. 确定dp数组(dp table)以及下标的含义
   • dp[i][0] 表示第 \(i\) 天持有股票所得现金
   • dp[i][1] 表示第 \(i\) 天不持有股票所得最多现金
2. 确定递推公式
   • dp[i][0] 可能是第 \(i-1\) 天就持有股票，那么就保持现状，所得现金就是昨天持有股票的所得现金 即: dp[i - 1][0]
   • dp[i][0] 也可能是第 \(i\) 天买入股票，所得现金就是昨天不持有股票的所得现金减去今天的股票价格 即: dp[i - 1][1] - prices[i]
   • dp[i][0] = max(dp[i-1][0],dp[i - 1][1] - prices[i])
   • dp[i][1] 可能是第 \(i-1\) 天就不持有股票，那么就保持现状，所得现金就是昨天持有股票的所得现金 即: dp[i - 1][1]
   • dp[i][1] 也可能是第 \(i-1\) 天卖出股票，所得现金就是昨天持有股票的所得现金加上今天的股票价格 即: dp[i - 1][0] + prices[i]
   • dp[i][1] = max(dp[i-1][1],dp[i-1][0] + prices[i])
3. dp数组的初始化
   • dp[0][0] 表示第 \(0\) 天买入股票剩余现金，即 dp[0][0] -= prices[0]
   • dp[0][1] 表示第 \(0\) 天不持有股票剩余现金，即 dp[0][1] = 0
4. 确定遍历顺序
   • 遍历顺序是从第 1 天往后每一天

   1for (int i = 1; i < len(prices); i++) {
   2 dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]); // 注意这里是和121. 买卖股票的最佳时机唯一不同的地方。
   3 dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i]);
   4}
   

5. 举例推导dp数组

翻译:

• "English" |