Leetcode 188: Best Time to Buy and Sell Stock IV - hard

Best Time to Buy and Sell Stock, leetcode 一共有6题。121、122、123、188、309、714。 其中121、122、123、188是一类（121交易一次、122交易任意多次、123交易两次，188交易k次）。 309是在前面四题的基础上，加了一个cool down。714则是加了交易成本。

所以前面四题可以由第四题的代码来实现。

思路如下：

1、状态

f[i][j] 代表的是到第j天，发生i次交易，可以得到的全局最大利润；g[i][j] 代表的是在第j天，进行第i次交易（在第j天，刚好发生交易）可以得到的local最大利润是多少。可以发现，f[i][j]是在g[i][j]的基础上进行更新，所以我们先更新g的值，再更新f的值。

2、转移方程

g[i][j] = max(f[i-1][j], g[i][j]) + prices[i]-prices[i-1]

temp = f[i-1][j]   (用temp来存储f[i-][j]的值）

f[i][j] = max(g[i][j], f[i][j])

因为对于每一个g和f来说，j都是固定的，变化的是i的情况。所以我们可以把上述的情况简化为g[i], f[i]，减少额外空间的使用。

3、初始化

g[i] = [0] * (k+1)

f[i] = [0] * (k+1)

temp = f[0]

4、return f[k]

注意点：可以提前判断k 是否大于天数的一半，因为如果大于天数的一半，意味着可以进行任意多次交易。直接用 profit += prices[i] - prices[i-1] （if prices[i] > prices[i-1])就行。

class Solution:
    def maxProfit(self, k: int, prices: List[int]) -> int:
        if not prices or not k: return 0
        profit = 0
        n = len(prices)
        if k >= n //2:
            for i in range(1,n):
                if prices[i] - prices[i-1]>0:
                    profit+=prices[i]-prices[i-1]

            return profit

        f = [0] * (k+1)
        g = [0] * (k+1)

        for i in range(1,n):
            diff = prices[i]-prices[i-1]
            temp = f[0]
            for kk in range(1,k+1):
                g[kk] = max(g[kk], temp,0) + diff
                temp = f[kk]
                f[kk] = max(f[kk], g[kk])
        return f[k]