股票买卖之动态规划
所属场景不同， 动规 dp 所代表的意义不同， 即使是同类型场景， 比如股票， 也要分具体场景赋予其意义，不可过度纠结别的题的意义， 以下几道题目是本人总结的关于股票买卖动态规划的实现， 在实现时本着当天可能具有的最少状态，定义dp数组，几道题目核心思想都趋于一致，理解水到渠成，我是感觉比官方题解更好理解
一、只交易一次
给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
"""
dp[i][j] 代表 第 i 天 结束 后 ，[j] 状态下可取得的最大值
dp[i][0] : 当天买入或者当天买了不合适， 保持不买
dp[i][1] : 当天卖出或者当天卖了不合适， 保持不卖
只买卖一次的话, dp[i][0] 应该保持最低买入价格， dp[i][1] 应该保持最大卖出价格，
"""
class Solution:
def maxProfit(self, prices: List[int]) -> int:
dp = [[0, 0] for _ in range(len(prices))]
dp[0][0] = -prices[0]
for i in range(1, len(prices)):
dp[i][0] = max(dp[i - 1][0], -prices[i])
dp[i][1] = max(dp[i - 1][1], prices[i] + dp[i - 1][0])
return dp[-1][1]
二、可以买卖多次
给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。
在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。
返回 你能获得的 最大 利润 。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
"""
dp[i][j] 代表 第 i 天 结束 后 ，[j] 状态下可取得的最大值
dp[i][0] : 当天买入或者当天买了不合适， 保持不买， 保持不买的话就是 dp[i - 1][0], 买了不合适的话， 说明昨天卖完后的钱（截止昨天的最大收益） - 今天买入的价格， 比昨天不卖的利润都低， 那说实话，亏了， 不能买 , 在上一道题中， 当天不合适买的情况是， 当天买入价格如果比以前买入价格高， 那么不合适买， 因为上一道题只能买卖一次， 那么动归dp就该符合只买卖一次的逻辑， 本题就不一样了， 本题可以买卖多次， 那么本题中买不买就不是论今天买入价格是不是比昨天低， 而是看今天买了后， 会不会有钱赚
dp[i][1] : 当天卖出或者当天卖了不合适， 保持不卖， 当天卖出就是昨天买入的最低价格 + 今天卖出的价格， 如果卖了所得利润， 还没昨天卖了高， 那就不卖， 保持昨天的利润
只买卖一次的话, dp[i][0] 应该保持最低买入价格， dp[i][1] 应该保持最大卖出价格，
"""
class Solution:
def maxProfit(self, prices: List[int]) -> int:
dp = [[0, 0] for _ in range(len(prices))]
dp[0][0] = -prices[0]
for i in range(1, len(prices)):
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[-1][-1]
"""
当 prices = [7,1,5,3,6,4] 时， 打印 dp 如下
[-7, 0]
[-1, 0]
[-1, 4]
[1, 4]
[1, 7]
[3, 7]
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]) 这一步， 会将历史收益都加起来， 保证动态规划的正确执行
"""
三、只可以买卖两次
给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
"""
只可以买两次， 那么当天有如下状态
0 ： 第一次买入, 同第一道只能买卖一次的题， dp[i][0]要保持最小值
1 ： 第一次卖出, 同第一道只能买卖一次的题， dp[i][1]要保持最大利润
2 ： 第二次买入, 只是在第一道题的基础上又进行了只买卖一次的操作， 相当于我已经有了一部分本金，但是在剩下的时间 里， 我只能进行一次股票交易
3 ： 第二次卖出, 讲解同 2
需要注意的是， 一天内就可以把两次交易都进行完成， 所以 dp[0][2] 初始化的时候， 也需要赋值 -prices[0], 初始化是递推的关键, 那么第0天的时候， 是非买不可的， 就算第0天买的亏了， 后边也可以迭代更新， 如果第0天不买， 那么第0天就不能卖， 相当于第0天的信息就没了， 所以是错误的。
注意：在 dp[i][2] = max(dp[i - 1][2], dp[i - 1][1] - prices[i]) 中， 第二次买卖必须是建立在第一次买卖的基础上的， 因为只能完成两笔交易， 所以必须第一笔交易完成后， 才能完成第二笔交易
"""
class Solution:
def maxProfit(self, prices) -> int:
dp = [[0] * 4 for _ in range(len(prices))]
dp[0][0] = -prices[0]
dp[0][2] = -prices[0]
for i in range(1, len(prices)):
dp[i][0] = max(dp[i - 1][0], -prices[i])
dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i])
dp[i][2] = max(dp[i - 1][2], dp[i - 1][1] - prices[i])
dp[i][3] = max(dp[i - 1][3], dp[i - 1][2] + prices[i])
return dp[-1][-1]
四、只可以买卖K次
给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iv
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
"""
只可以买卖K次的话， 每天都有 2 * K 个状态， 分别为 第1次买， 第一次卖 ... 第K次买， 第K次卖
只可以买卖K次规律是从只买两次总结来的， 需要注意的是， dp[i][0] = max(dp[i - 1][0], -prices[i]) 这个式子没办法加到通项公式中， 只能单拎出来， 其它的满足：
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1] + (-1)**(j+1) * prices[i])
"""
class Solution:
def maxProfit(self, k, prices) -> int:
dp = [[0] * (2 * k) for _ in range(len(prices))]
for i in range(0, 2 * k, 2):
dp[0][i] = -prices[0]
for i in range(1, len(prices)):
dp[i][0] = max(dp[i - 1][0], -prices[i])
for j in range(1, 2 * k):
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1] + (-1)**(j+1) * prices[i])
return dp[-1][-1]
五、有冷冻期
给定一个整数数组prices，其中第 prices[i] 表示第 i 天的股票价格 。
设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-cooldown
"""
dp[i][j] 表示 ： 第 i 天结束后， [j] 状态 当天可以获得的最大利润
j 分为如下几种情况
0 : 表示， 当前天是 买入 状态 ， 那么当天状态可保持前一天买入或者当天买入
dp[i][0] = max(dp[i - 1][0], dp[i - 1][2] - prices[i])
1 : 表示，当前天是 卖出 状态 卖出后处于冷冻期， 但是当天不是冷冻期, 如果当天卖了后亏了， 那肯定不能卖， dp[i] [1] 就应该保持前一天状态， 如果当天卖了能赚， 那么当卖则卖， 所以
dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i])
2 : 表示， 当前天是冷冻期， 说明前一天 卖出了， 那么冷冻期值就应该为前一天卖出的金额
dp[i][2] = dp[i - 1][1]
"""
class Solution:
def maxProfit(self, prices) -> int:
dp = [[0] * 3 for i in range(len(prices))]
dp[0][0] = -prices[0]
for i in range(1, len(prices)):
dp[i][0] = max(dp[i - 1][0], dp[i - 1][2] - prices[i])
dp[i][1] = max(dp[i - 1][0] + prices[i], dp[i - 1][1])
dp[i][2] = dp[i - 1][1]
return return max(dp[-1])
if __name__ == '__main__':
solution = Solution()
arr = [2,1,2,0,1]
solution.maxProfit(arr)
六、含手续费
给定一个整数数组 prices，其中 prices[i]表示第 i 天的股票价格 ；整数 fee 代表了交易股票的手续费用。
你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。
返回获得利润的最大值。
注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-transaction-fee
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
"""
本题相比第二题（可以无限制买卖多次）， 只是多了个手续费， 并且一笔交易只有一次手续费， 那么只需要规定在卖出股票的时候， 交一笔手续费即可
"""
class Solution:
def maxProfit(self, prices, fee: int) -> int:
dp = [[0, 0] for _ in range(len(prices))]
dp[0][0] = -prices[0]
for i in range(1, len(prices)):
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] - fee + prices[i])
return dp[-1][-1]
|