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

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