Best time to buy and sell stock IV

Question

Design an algorithm to find the maximum profit. You may complete at most k transactions.

Thoughts

reference reference2

特殊DP方法

传统的动态规划我们会这样想，到第i天时进行j次交易的最大收益，要么等于到第i-1天时进行j次交易的最大收益（第i天价格低于第i-1天的价格），要么等于到第i-1天时进行j-1次交易，然后第i天进行一次交易（第i天价格高于第i-1天价格时）。于是得到动规方程如下（其中diff = prices[i] – prices[i – 1]）：

profit[i][j] = max(profit[i – 1][j], profit[i – 1][j – 1] + diff)

看起来很有道理，但其实不对，为什么不对呢？因为diff是第i天和第i-1天的差额收益，如果第i-1天当天本身也有交易呢，那么这两次交易就可以合为一次交易，这样profit[i – 1][j – 1] + diff实际上只进行了j-1次交易，而不是最多可以的j次，这样得到的最大收益就小了。

那么怎样计算第i天进行交易的情况的最大收益，才会避免少计算一次交易呢？我们用一个局部最优解和全局最有解表示到第i天进行j次的收益，这就是该动态规划的特殊之处。

用local[i][j]表示到达第i天时，最多进行j次交易的局部最优解（第i天必须交易）；用global[i][j]表示到达第i天时，最多进行j次的全局最优解。它们二者的关系如下（其中diff = prices[i] – prices[i – 1]）：

local[i][j] = max(global[i – 1][j – 1] + max(diff, 0), local[i – 1][j] + diff)
global[i][j] = max(global[i – 1][j], local[i][j])

其中的local[i – 1][j] + diff就是为了避免第i天交易和第i-1天交易合并成一次交易而少一次交易收益。

Solution

class Solution:
    """
    @param k: an integer
    @param prices: a list of integer
    @return: an integer which is maximum profit
    """
    def maxProfit(self, k, prices):
        # write your code here
        if not prices:
            return 0
        length = len(prices)
        if k >= length:
            return self.maxProfit2(prices)
        lDP = [[ 0 for i in range(k+1)] for j in range(length)]
        gDP = [[ 0 for i in range(k+1)] for j in range(length)]

        for i in range(1, length):
            diff = prices[i] - prices[i-1]
            for j in range(1, k+1):
                lDP[i][j] = max(gDP[i-1][j-1] + max(diff, 0), lDP[i-1][j] + diff)
                gDP[i][j] = max(gDP[i-1][j], lDP[i][j])

        return gDP[length-1][k]

    def maxProfit2(self, prices):
        # write your code here
        maxProfit = 0
        for i in range(1, len(prices)):
            if prices[i] > prices[i-1]:
                maxProfit += prices[i] - prices[i-1]
        return maxProfit