AcWing 1057. 股票买卖 IV(Python)
原题链接
中等
作者:
习学学
,
2021-02-10 13:56:57
,
所有人可见
,
阅读 326
Python 代码
N, k = map(int, input().split())
nums = [0] + list(map(int, input().split()))
# dp[j][0] 代表已经进行j次买卖,当前手中无货的最大利润
# dp[j][1] 代表已经进行j次买卖,当前手中有货的最大利润
dp = [[-float('inf'), -float('inf')] for _ in range(k+1)]
dp[0][0] = 0 # 对于第i天,手中无货为0
for i in range(1, N+1):
for j in range(1, k+1):
dp[j][0] = max(dp[j][0], dp[j][1] + nums[i])
dp[j][1] = max(dp[j][1], dp[j-1][0] - nums[i])
res = 0
for i in range(1, k+1):
res = max(res, dp[i][0])
print(res)
dp[j][1] = max(dp[j][1], dp[j-1][0] - nums[i]) 其中dp[j-1][0]应该变成了当前层的状态了呀 不应该等价变形 要为dp[i-1][j-1][0] 即上一层的状态