LeetCode第188题分析

题目

给定一个数组prices,长为n,第i个元素表示股票在第i天的价格。
设计算法获得最大利润,至多产生k次交易(k买k卖)。
不能同时参与多次交易,买进之前要把之前的卖出。

分析

动态规划

dp[i][j]表示从第0天到第j天,至多交易i次时能够得到的最大利润。显然第0行和第0列全是零。
tmp[i][j]表示从第0天到第j天,至多交易i-1次,并且再有一次买入时的最大利润。第0行无意义。
按照先行后列的顺序更新表。取值范围是i=[1,k];j=[1,n-1]。

更新dp[i][j]

dp[i][j] = max(dp[i][j-1], price[j] + tmp[i][j-1])
当第j天不抛售时,最大利润为第j-1天的最大利润;
当第j天抛售时,最大利润为第j-1天至多交易i-1次,并且再买入一次的最大利润。
二者取最大值。

更新tmp[i][j]

tmp[i][j] = max(tmp[i][j-1], dp[i-1][j] - prices[j]),
当第j天不买入时,最大利润为第j-1天的最大利润;
当第j天买入时,最大利润为第至多交易i-1次的最大利润减去买入价格。
二者取最大值。

边界条件

dp初始化为0,并且更新dp时只会变大,第0行和第0列不会更新。
tmp初始化为0,发现当j=0时应该更新但没有更新,所以在每行循环之前要加上tmp[i][0] = dp[i-1][0] - prices[0]

简化

dp[i][j]和tmp[i][j]的更新只会与dp[i][j-1],dp[i-1][j]和tmp[i][j-1]有关, 所以dp可以压缩为1*n的数组,tmp可以只用一个变量表示。
注意到最多只会产生div(n, 2)对交易,所以当k>=div(n, 2)时的最大利润为所有股票价格上升产生的利润和。

复杂度

时间复杂度O(kn),空间复杂度O(n)。