登录
  • #刷题
  • #学python/perl

请教‌‌‍‍‌‍‍‌‍‌‌‍‍‌‌‍‌‌‌‍‌‌‍‍‌‍‍‍‌‌‌‌, 关于best time to buy and sell stock iv

fasionfans
477
0
leetcode.com

这道题, 看了leetcode官方的解体思路, 基本上是3维dp, 也可以说成2维, 因为第3维只有0或1两种可能。dp表示: dp[day_number][used_transaction_number][stock_holding_status] . 但是有一点不太理解, 它说如果buying, 状态转移方程是dp[j][1]=dp[i-1][j-1][0]+prices, 我的理解是截止第i-1天一共做了j-1次交易, 第i-1天时未持有股票, 第i天做了买入操作, 那么截止第i 天一共做了j次操作, 获得的总利润是截止第i-1天获得的利润减去prices, 也就是第i天买入股票的钱, 这个能明白; 但是关于sellling, 官方给出的公式是dp[j][0]=dp[i-1][j][1]+prices, 我就不太明白, 按照上面buying的思路, 不应该是dp[j][0]=dp[i-1][[1]+prices吗? 为什么取dp[i-1][[color=#ff00ff]j][[/color]1] instead of dp[i-1][j-1][1]? 如果截止第i-1天已经完成了j次操作, 那么第i天就没法再做一次操作了啊? 而且我理解dp[i-1][j][1] 的意思是在截止第i-1天还hold着股票, 那么必须在第i天有个卖出的操作, 不知道我理解的对吗? 求大神解惑。。。谢谢!

Buying, when j>0:

dp[j][1] = dp[i-1][j-1][0]-prices[i】[br]
Selling:

dp[j][0] = dp[i-1][j][1]+prices[i】[br]
官方完整代码:

class Solution:

def maxProfit(self, k: int, prices: List[int]) -> int:

n = len(prices)

# solve special cases

if not prices or k==0:

return 0

if 2*k > n:

res = 0

for i, j in zip(prices[1:], prices[​:-1]):

res += max(0, i - j)

return res

# dp[used_k][ishold] = balance

# ishold: 0 nothold, 1 hold

dp = [[[-math.inf]*2 for _ in range(k+1)] for _ in range(n)]

# set starting value

dp[0][0][0] = 0

dp[0][1][1] = -prices[0]

# fill the array

for i in range(1, n):

for j in range(k+1):

# transition equation

dp[j][0] = max(dp[i-1][j][0], dp[i-1][j][1]+prices)

# you can't hold stock without any transaction

if j > 0:

dp[j][1] = max(dp[i-1][j][1], dp[i-1][j-1][0]-prices)

res = max(dp[n-1][j][0] for j in range(k+1))

return res
0条回复
热度排序

发表回复