九十二、动态规划系列之股票问题（上）
「@Author：Runsen」
动态规划必须要面对股票系列，背包系列差不多了，那就上吧。
股票买卖这一类的问题，都是给一个输入数组，里面的每个元素表示的是每天的股价，并且你只能持有一支股票（也就是你必须在再次购买前出售掉之前的股票），一般来说有下面几种问法：
- 只能买卖一次
- 只能买卖两次
- 可以买卖无数次
- 可以买卖 k 次
- 买 N 次加 CD 冷却时间
- 买 N 次加手续费
需要你设计一个算法去获取最大的利润。
买卖股票的最佳时机（买一次）
这是 Leetcode 的第 121 题： 买卖股票的最佳时机（买一次）
输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。
思路
示例：[7,1,5,3,6,4]
(1) i = 0，min = 7，result = 0；
(2) i = 1，min = 1，result = 0；
(3) i = 2，min = 1，result = 5 - 1 = 4；
(4) i = 3，min = 1，result = 4；
(5) i = 4，min = 1，result = 6 - 1 = 5；
(6) i = 5，min = 1，result = 5；
首先，定义 dp[i] 的含义为：第 i 天的最大利润。
一次买卖股票得到最大利润的当然是历史最低点买，因此思路为：遍历一遍数组，计算每次到当天为止的最小股票价格和最大利润。
因此状态转移方程：比较前一天的利润和今天的卖出减去最小的股票价格。
然后问题转移到了求minprice历史最低点，因此转化为求滑动数组的最小值的问题，方法就是假设第一个为最小值，不断地比较替换。
边界问题：dp = [0] * n
class Solution:
def maxProfit(self, prices: List[int]) -> int:
# dp的状态转移方程：dp[i] = max(dp[i-1],prices[i]-minprice)
n = len(prices)
if n == 0: return 0
dp = [0] * n
minprice = prices[0]
for i in range(1,n):
minprice = min(minprice,prices[i])
dp[i] = max(dp[i-1],prices[i]-minprice)
return dp[-1]
买卖股票的最佳时机（买 N 次）
这是 Leetcode 的第 122 题： 买卖股票的最佳时机（买 N 次）
输入: [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。
你只能
你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
由于可以买卖多次，那么 dp 就需要开一个维度来表示当天是买还是卖，因此是动态规划二维数组 dp。
dp[i][0] 表示前 i 天的最大利润，第 i 天不买，那么 dp 转移方程取决于 i-1 天是有股票还是没有股票。
dp[i][1] 表示前 i 天的最大利润，第 i 天必须买, 那么 dp 转移方程取决于 i-1 天是有股票还是没有股票
最后，第 i 天不可以买股票。当然是dp[i][0] 比dp[i][1]大
对此，还有贪心的做法，找到所有的上升区间，计算每个上升区间的价格差,直接节约了空间复杂度为 O(1)，也就是，只有明天比我今天的开的高，我就卖。
还可以对第一种常规方法进行空间优化，因此我们不需要第i-1天的最大利润。我们只需要使用两个变量储存第i天没有股票的最大利润和有股票的最大利润，然后不断地维护更新。
class Solution:
def maxProfit(self, prices: List[int]) -> int:
n = len(prices)
if n == 0: return 0
dp = [[0]*2 for _ in range(n)]
dp[0][0] = 0
dp[0][1] = -prices[0]
for i in range(1,n):
dp[i][0] = max(dp[i-1][0],dp[i-1][1]+prices[i])
dp[i][1] = max(dp[i-1][0]-prices[i],dp[i-1][1])
return dp[-1][0]
# 贪心做法
n = len(prices)
profit = 0
if n == 0 : return 0
for i in range(1,n):
if prices[i] > prices[i-1]:
profit += prices[i] - prices[i-1]
return profit
# 最好的做法就是有一个变量储存没有股票的最大利润和有股票的最大利润，然后不断地维护
# cash表示第i天结束，没有股票的最大利润
# hold表示第i天结束，有股票的最大利润
cash, hold = 0, -prices[0]
for i in range(1,len(prices)):
cash = max(cash,hold+prices[i])
hold = max(hold,cash-prices[i])
return cash
买卖股票的最佳时机（买 2 次）
这是 Leetcode 的第 123 题：买卖股票的最佳时机（买 2 次）
输入：prices = [3,3,5,0,0,3,1,4]
输出：6
解释：在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。
随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
与第二个不同在于，第二题你可以买无数次，但是现在只给你买 2 次。
我们直接把 2 次变成 K 次，变成第四题。因此变成了动态规划三维 dp 数组，多用一个维度定义了次数。
所以定义状态转移数组dp[天数][卖出的次数][当前是否持股]
状态的dp[i][k][XX]定义就是：i 表示第i天的最大利润，k表示第i天之前你买卖的次数，X 表示第i天是否有股票 0 ，1。在这里的 K 是 2。
具体一天结束时的 5 种状态：
- 未持股，未卖出过股票：说明从未进行过买卖，利润为 0。
dp[i][0][0]=0 - 未持股，卖出过 1 次股票：可能是昨天有股票，今天卖出，也可能昨天也未持股，但是之前卖出过。
dp[i][1][0]=max(dp[i-1][0][1]+prices[i],dp[i-1][1][0]) - 未持股，卖出过 2 次股票:可能是昨天有股票，今天卖出，昨天还卖出过 1 次股票，也可能是昨天也未持股，但是之前卖出过 2 次。
dp[i][2][0]=max(dp[i-1][1][1]+prices[i],dp[i-1][2][0]) - 持股，未卖出过股票：可能昨天没有买股票，就是今天买的，也可能是之前买的，昨天就持股，所有今天也持股。
dp[i][0][1]=max(dp[i-1][0][0]-prices[i],dp[i-1][0][1]) - 持股，卖出过 1 次股票：可能是今天买的，但是在昨天之前卖出过 1 次股票，也可能是之前买了股票，也卖出过 1 次股票，昨天是持股状态。
dp[i][1][1]=max(dp[i-1][1][0]-prices[i],dp[i-1][1][1])
加上之前的状态转移方程：
第 i 天（未持股），状态转移方程就是昨天未持股的最大利润，和昨天持股的最大利润加上今天卖出。
第 i 天（持股），状态转移方程就是昨天持股的最大利润，和昨天未持股的最大利润加上今天买入。
class Solution:
def maxProfit(self, prices: List[int]) -> int:
if not prices:
return 0
n = len(prices)
# 初始化状态
dp = [[[0]*2 for _ in range(3)] for _ in range(n)]
for k in range(3):
# 第一天买入股票
dp[0][k][1] = -prices[0]
# 从 i=1 处开始迭代
for i in range(1, n):
for k in range(1, 3):
dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1]+prices[i])
dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0]-prices[i])
return dp[-1][2][0]
因此毕竟是买卖 2 次，在第二次买的时候，用第一次的挣到的钱抵消了一部分第二次买的钱
class Solution:
def maxProfit(self, prices: List[int]) -> int:
n = len(prices)
buy1 = buy2 = -prices[0]
sell1 = sell2 = 0
for i in range(1, n):
buy1 = max(buy1, -prices[i])
sell1 = max(sell1, buy1 + prices[i])
buy2 = max(buy2, sell1 - prices[i])
sell2 = max(sell2, buy2 + prices[i])
rbueturn sell2
买卖股票的最佳时机（买 k 次）
这是 Leetcode 的第 188 题： 买卖股票的最佳时机（买 k 次）
输入：k = 2, prices = [3,2,6,5,0,3]
输出：7
解释：在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。
随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。
这道题理论上和 LeetCode 123（交易次数最多为 2） 的解法一样，但是直接提交容易出现超内存的错误，是测试用例提供的 K 太大导致的。
因此,需要对 K 进行处理，有效的交易由买入和卖出构成，至少需要两天；反之，当天买入当天卖出则视为一次无效交易。因此 K 必须小于n//2 。
如果题目给定的最大交易次数 k<=n//2，这个 k 是可以有效约束交易次数的，本题为 LeetCode 123（交易次数为2次）；如果给定的 k>n//2 ，本题为 LeetCode 122（不限交易次数） 。
整体思路是判断k 和 n//2 的大小关系，两个分支分别用 LeetCode 123和 LeetCode 122 的代码解决，可有效防止内存超出。
class Solution:
def maxProfit(self, k: int, prices: List[int]) -> int:
if k == 0 or len(prices) < 2:
return 0
n = len(prices)
res = []
# 如果k的次数大于n//2，那么就是直接计算利润，第一天买，第二天就卖，然后第二天在买。
if k > n // 2:
# 下面就是Leetcode第122的代码
max_profit = 0
for i in range(1,n):
profit = prices[i] - prices[i - 1]
# 如果第二天比第一天高，那就直接加入
if profit > 0:
max_profit += profit
return max_profit
# 下面就是Leetcode第123的代码
dp = [[[0] * 2 for _ in range(k + 1)] for _ in range(n)]
for i in range(k + 1):
# 第一天买入股票
dp[0][i][1] = - prices[0]
for i in range(1, n):
for k in range(1, k+1):
dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1]+prices[i])
dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0]-prices[i])
# 求dp[i][k][0] 的最大，这里直接开数组 , 比较每一个次数的最大利润
for m in range(k + 1):
res.append(dp[-1][m][0])
return max(res)
- END -
腾讯云开发者
