LeetCode 题解:188. 买卖股票的最佳时机 IV,动态规划,JavaScript,详细注释
原题链接:188. 买卖股票的最佳时机 IV
解题思路:
该题与123. 买卖股票的最佳时机 III类似,只是交易次数有2
次改为了k
次。如果没有思路可以先看123
题的[题解](https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iii/solution/leetcodeti-jie-123-mai-mai-gu-piao-de-zu-xf0n/)。
截至第
i
天,当前已经交易过2
次,每次交易都可以买(支出prices[i]
)或卖(收入prices[i]
),因此可以用长度为k * 2
的dp
数组递推。每种交易,都要在之前交易的基础上进行,例如只有买入后,才可以卖出。因此状态转移方程为:
复制代码
卖出
k
次获得的利润一定是最多的,因此最大利润就在dp[dp.length - 1]
。
复制代码
版权声明: 本文为 InfoQ 作者【Lee Chen】的原创文章。
原文链接:【http://xie.infoq.cn/article/63e54dde5fd5a6363284a9dcf】。文章转载请联系作者。
评论