打卡记录

买卖股票的最佳时机 IV（状态机DP）

链接

class Solution:
    def maxProfit(self, k: int, prices: List[int]) -> int:
        n = len(prices)
        max = lambda x, y: x if x > y else y
        f = [[-0x3f3f3f3f] * 2 for _ in range(k + 2)]
        for i in range(k + 2): f[i][0] = 0
        for x in prices:
            for j in range(k + 1):
                f[j + 1][0] = max(f[j + 1][0], f[j][1] + x)
                f[j + 1][1] = max(f[j + 1][1], f[j + 1][0] - x)
        return f[k + 1][0]