# 只和过去一个时间有关的, 空间可以优化
class Solution:
def maxProfit(self, prices: List[int]) -> int:
dp = [[0] * 2 for _ in range(len(prices))]
dp[0][0] = -prices[0]
dp[0][1] = 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])
return dp[-1][1]
时间复杂度：O(n)
空间复杂度：O(n)
follow up-股票买卖类
可以进行无数笔交易，注意先买后卖
递增区间的和
dp含义不变，只是公式有更新
class Solution:
def maxProfit(self, prices: List[int]) -> int:
dp = [[0] * 2 for _ in range(len(prices))]
dp[0][0] = -prices[0]
dp[0][1] = 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]
时间复杂度：O(n)
空间复杂度：O(n)
class Solution:
def maxProfit(self, prices: List[int]) -> int:
if not prices:
return 0
res = 0
for i in range(1, len(prices)):
if prices[i] >= prices[i-1]: # 递增区间
res = res + prices[i] - prices[i-1] # 和
else:
continue
return res
最多完成两笔交易
dp含义差不多？类似问题中，二维dp中的第二维是某种状态枚举
class Solution:
def maxProfit(self, prices: List[int]) -> int:
if len(prices) <= 1:
return 0
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 max(dp[-1][1], dp[-1][3])
时间复杂度：O(n)
空间复杂度：O(n), 可继续优化至O(1)
最多完成k笔交易
把最多完成两笔交易中的2进一步参数化
class Solution:
def maxProfit(self, k: int, prices: List[int]) -> int:
if len(prices) <= 1:
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]
时间复杂度：O(n)
空间复杂度：O()
含冷冻期
注意状态划分与转移，仍然是第二维是状态
class Solution:
def maxProfit(self, prices: List[int]) -> int:
if len(prices) <= 1:
return 0
dp = [[0] * 4 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][2]-prices[i]) # hold, 之前持有或非冷冻期买入
dp[i][1] = dp[i-1][0] + prices[i] # sell, 前一天持有后卖出，卖出后进入的是冷冻状态，因此没有dp[i-1][1]
dp[i][2] = max(dp[i-1][2], dp[i-1][1]) # cool, 注意该状态是冷冻或冷冻期之后可买入的状态， 因此还要和自己过去比较
return max(dp[-1][1], dp[-1][2])
时间复杂度：O(n)
空间复杂度：O()
含交易手续费
和122类似，卖出时加上手续费
class Solution:
def maxProfit(self, prices: List[int], fee: int) -> int:
if len(prices) <= 1:
return 0
dp = [[0] * 2 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] - fee)
return dp[-1][1]