通过leetcode记录自己每天坚持刷题，以此监督自己的学习。不能放假了就懈怠😁
题目传送地：剑指 Offer 63. 股票的最大利润（middle）
假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可能获得的最大利润是多少？
示例 1:
输入: [7,1,5,3,6,4] 输出: 5 解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 =6）的时候卖出，最大利润 = 6-1 = 5 。注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。
这个题没什么好说的，但是呢刷到了这个题我就索性想着重新把股票问题刷一遍，温习温习，好久不做即使会也会卡住
class Solution:
def maxProfit(self, prices: List[int]) -> int:
if len(prices)==0:
return 0
low_price=prices[0]
ans=0
temp_ans=0
for i in range(1,len(prices)):
if prices[i]<low_price:
low_price=prices[i]
else:
temp_ans=prices[i]-low_price
ans=max(ans,temp_ans)
return ans
题目传送地：122. 买卖股票的最佳时机 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数组的含义：
dp[i][0] 表示第i天持有股票所得现金。
dp[i][1] 表示第i天不持有股票所得最多现金
因此推导公式则有
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
class Solution:
def maxProfit(self, prices: List[int]) -> int:
length = len(prices)
dp = [[0] * 2 for _ in range(length)]
dp[0][0] = -prices[0]
dp[0][1] = 0
for i in range(1, length):
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]
题目传送地：123. 买卖股票的最佳时机 III
给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1:
输入：prices = [3,3,5,0,0,3,1,4] 输出：6 解释：在第 4 天（股票价格 = 0）的时候买入在第 6天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3
随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。
Ⅲ跟Ⅱ的区别是Ⅲ最多可以完成两笔，那么不同之处就是dp数组的列有变化，要细分为
没有操作
第一次买入
第一次卖出
第二次买入
第二次卖出
因此dp的状态转移方程可这样分析：
达到dp[i][1]状态，有两个具体操作：
操作一：第i天买入股票了，那么dp[i][1] = dp[i-1][0] - prices[i]
操作二：第i天没有操作，而是沿用前一天买入的状态，即： dp[i][1] = dp[i - 1][1]
即dp[i][1] = max(dp[i-1][0] - prices[i], dp[i - 1][1]);
达到dp[i][2]也有两个操作：
操作一：第i天卖出股票了，那么dp[i][2] = dp[i - 1][1] + prices[i]
操作二：第i天没有操作，沿用前一天卖出股票的状态，即：dp[i][2] = dp[i - 1][2] 所以dp[i][2] =max(dp[i - 1][1] + prices[i], dp[i - 1][2])
.
..
dp[i][3] = max(dp[i - 1][3], dp[i - 1][2] - prices[i]);dp[i][4] = max(dp[i - 1][4], dp[i - 1][3] + prices[i]);
class Solution:
def maxProfit(self, prices: List[int]) -> int:
if len(prices) == 0:
return 0
dp = [[0] * 5 for _ in range(len(prices))]
dp[0][1] = -prices[0]
dp[0][3] = -prices[0]
for i in range(1, len(prices)):
dp[i][0] = dp[i-1][0]
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])
dp[i][4] = max(dp[i-1][4], dp[i-1][3] + prices[i])
return dp[-1][4]
题目传送地 188. 买卖股票的最佳时机 IV
给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1：
输入：k = 2, prices = [2,4,1] 输出：2 解释：在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天
(股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。
该题跟三不同的是至多k笔，那么只需在Ⅲ的基础稍加改动即可
0 表示不操作
1 第一次买入
2 第一次卖出
3 第二次买入
4 第二次卖出
…
除了0以外，偶数就是卖出，奇数就是买入
class Solution:
def maxProfit(self, k: int, prices: List[int]) -> int:
if len(prices) == 0:
return 0
dp = [[0] * (2*k+1) for _ in range(len(prices))]
for j in range(1, 2*k, 2):
dp[0][j] = -prices[0]
for i in range(1, len(prices)):
for j in range(0, 2*k-1, 2):
dp[i][j+1] = max(dp[i-1][j+1], dp[i-1][j] - prices[i])
dp[i][j+2] = max(dp[i-1][j+2], dp[i-1][j+1] + prices[i])
return dp[-1][2*k]
题目传送地：309. 最佳买卖股票时机含冷冻期
给定一个整数数组prices，其中第 prices[i] 表示第 i 天的股票价格 。
设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1:
输入: prices = [1,2,3,0,2] 输出: 3 解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]
在股票问题Ⅱ的基础上增添了含冷冻期，不难发现其实就是dp数组的状态又多了几个，但是第一次看到这个题其实很难把每个状态都划分清楚
标准划分为
状态一：买入股票状态（今天买入股票，或者是之前就买入了股票然后没有操作）
卖出股票状态，这里就有两种卖出股票状态
- 状态二：两天前就卖出了股票，度过了冷冻期，一直没操作，今天保持卖出股票状态
- 状态三：今天卖出了股票
状态四：今天为冷冻期状态，但冷冻期状态不可持续，只有一天！
操作一：前一天就是持有股票状态（状态一），dp[i][0] = dp[i - 1][0]
操作二：今天买入了，有两种情况
- 前一天是冷冻期（状态四），dp[i - 1][3] - prices[i]
- 前一天是保持卖出股票状态（状态二），dp[i - 1][1] -prices[i]
所以操作二取最大值，即：max(dp[i - 1][3], dp[i - 1][1]) - prices[i]
那么dp[i][0] = max(dp[i - 1][0], max(dp[i - 1][3], dp[i - 1][1]) - prices[i]);
操作一：前一天就是状态二
操作二：前一天是冷冻期（状态四）
dp[i][1] = max(dp[i - 1][1], dp[i -1][3]);
达到今天就卖出股票状态（状态三），即：dp[i][2] ，只有一个操作：
操作一：昨天一定是买入股票状态（状态一），今天卖出
即：dp[i][2] = dp[i - 1][0] + prices[i]
达到冷冻期状态（状态四），即：dp[i][3]，只有一个操作：
操作一：昨天卖出了股票（状态三）
dp[i][3] = dp[i - 1][2];
因此
有递推公式
dp[i][0] = max(dp[i - 1][0], max(dp[i - 1][3], dp[i - 1][1]) - prices[i]) # 买入状态
dp[i][1] = max(dp[i - 1][1], dp[i - 1][3] ) # 保持卖出状态
dp[i][2] = dp[i - 1][0] + prices[i] # 今天卖出
dp[i][3] = dp[i - 1][2] # 冷冻
class Solution:
def maxProfit(self, prices: List[int]) -> int:
n = len(prices)
if n == 0:
return 0
dp = [[0] * 4 for _ in range(n)]
dp[0][0] = -prices[0] # 持有状态初始化
for i in range(1, n):
dp[i][0] = max(dp[i-1][0], max(dp[i-1][3], dp[i-1][1]) - prices[i])
dp[i][1] = max(dp[i-1][1], dp[i-1][3])
dp[i][2] = dp[i-1][0] + prices[i]
dp[i][3] = dp[i-1][2]
return max(dp[n-1][3], dp[n-1][1], dp[n-1][2])
题目传送地：714. 买卖股票的最佳时机含手续费
给定一个整数数组 prices，其中 prices[i]表示第 i 天的股票价格 ；整数 fee 代表了交易股票的手续费用。
你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。
返回获得利润的最大值。
注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。
示例 1：
输入：prices = [1, 3, 2, 8, 4, 9], fee = 2 输出：8 解释：能够达到的最大利润: 在此处买入
prices[0] = 1 在此处卖出 prices[3] = 8 在此处买入 prices[4] = 4 在此处卖出 prices[5]
= 9 总利润: ((8 - 1) - 2) + ((9 - 4) - 2) = 8
这个题跟Ⅱ的区别就是再卖出的时候多了一个手续费
因此代码就一个变化就足够了，但是如果使用贪心的话会多考虑一点
class Solution:
def maxProfit(self, prices: List[int], fee: int) -> int:
n = len(prices)
dp = [[0] * 2 for _ in range(n)]
dp[0][0] = -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][1], dp[i-1][0] + prices[i] - fee)
return max(dp[-1][0], dp[-1][1])