示例 1:
输入:k = 2, prices = [2,4,1]
输出:2
解释:在第 1 天 (股票价格 = 2) 的时候买入,在第 2 天 (股票价格 = 4) 的时候卖出,这笔交易所能获得利润 =...示例 2:
输入:k = 2, prices = [3,2,6,5,0,3]
输出:7
解释:在第 2 天 (股票价格 = 2) 的时候买入,在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润...而对于
,它的值为
,即「我们在第0天以
的价格买入股票」是唯一满足手上持有股票的方法。
对于
,同理我们可以将所有的
设置为一个非常小的值,表示不合法的状态。...而对于
,它的值为
,即「我们在第
天不做任何事」是唯一满足手上不持有股票的方法。
在设置完边界之后,我们就可以使用二重循环,在
的范围内进行状态转移。...,
和
都从
以及
转移而来,因此我们可以使用一维数组而不是二维数组进行状态转移,即:
这样的状态转移方程会因为状态的覆盖而变得不同。