代码随想录算法训练营 Day 36
Published:
动态规划五部曲
- 确定dp数组以及下标的含义
- 确定递推公式
- 初始化dp数组
- 确定遍历顺序
- 举例推导dp数组
第5步随着输入不同而变化，因此在此省去
Q1. LeetCode 188
与LeetCode 123类似，只是允许k次买卖交易，所以一共有$2*k+1$种状态
前四步：（采用滚动数组）
- 使用一维的dp数组，dp[i]表示不同状态下最多有多少钱。状态可分为从来没有股票，第一次有股票，第一次没有股票，第二次有股票，第二次没有股票…因此状态数为$2*k+1$
- 递推公式：每种状态依然是两种情况：当天进行买卖或者延续前一天状态。并且可以看出奇数索引可能含有股票买入，偶数索引（除0以外）含有股票卖出
- 初始化：整体初始化为0，所有奇数索引均初始化为-prices[0]
- 遍历顺序：从前向后遍历
一维数组是从二维数组压缩而来的
class Solution:
def maxProfit(self, k: int, prices: List[int]) -> int:
dp = [0] * (2 * k + 1)
for i in range(1, 2 * k + 1, 2):
dp[i] = -prices[0]
for i in range(1, len(prices)):
for j in range(1, 2 * k + 1):
if j % 2 == 0:
dp[j] = max(dp[j], dp[j - 1] + prices[i])
else:
dp[j] = max(dp[j], dp[j - 1] - prices[i])
return dp[-1]
复杂度分析
时间复杂度：O($n \times k$) 空间复杂度：O($k$)
Q2. LeetCode 309
因为冷静期的缘故，所以对于未持有股票的情况要分开进行考虑（是否处于冷静期）
class Solution:
def maxProfit(self, prices: List[int]) -> int:
n = len(prices)
# 三种状态：0 - 不持有股票并且是当天卖掉；1 - 持有股票；2 - 不持有股票并且不处于冷静期
dp = [[0] * 3 for _ in range(n)]
dp[0][1] = -prices[0]
for i in range(1, n):
dp[i][0] = dp[i - 1][1] + prices[i]
dp[i][1] = max(dp[i - 1][1], dp[i - 1][2] - prices[i])
dp[i][2] = max(dp[i - 1][2], dp[i - 1][0])
return max(dp[-1][0], dp[-1][2])
复杂度分析
时间复杂度：O($n$) 空间复杂度：O($n \times 3$)
Q3. LeetCode 714
因为引入了手续费，所以在某一天没有持有股票并且符合这一天卖掉的情况，此时$dp[i][0] = dp[i-1][1] + prices[i] - fee$
class Solution:
def maxProfit(self, prices: List[int], fee: int) -> int:
n = len(prices)
dp = [[0] * 2 for _ in range(n)]
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] - fee)
dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i])
return dp[-1][0]
复杂度分析
时间复杂度：O($n$) 空间复杂度：O($n \times 2$)