关于leetcode:leetcode-188-题

8次阅读

共计 1335 个字符，预计需要花费 4 分钟才能阅读完成。

明天的每日一题

You are given an integer array prices where prices[i] is the price of a given stock on the ith day, and an integer k.

Find the maximum profit you can achieve. You may complete at most k transactions.

Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).

Input: k = 2, prices = [2,4,1]
Output: 2
Explanation: Buy on day 1 (price = 2) and sell on day 2 (price = 4), profit = 4-2 = 2.

咱们保护两个数组 buy 和 sell 别离记录以后持有和卖出时的收益
buy[i] 代表在第 i 天买入后手里的钱
sell[i] 代表在第 i 天卖出后手里的钱
因为有 k 手交易的限度，将动静布局数组转化为矩阵, 第二个维度代表交易的次数，这里交易的定义是残缺的一次买入后又卖出记为一次，由此可得状态转移方程

buy[i][j] = max{buy[i-1][j], sell[i-1][j]-prices[i]}

buy[i-1][j]前一天买入后当天不操作
sell[i-1][j]-prices[i] 前一天卖出后明天买入

sell[i][j] = max{buy[i-1][j-1] + price[i], sell[i-1][j]}

buy[i-1][j-1]前一天买入明天卖出，须要留神的是因为实现了一次交易，所以对应的前日操作应该是 buy[i-1][j-1]
sell[i-1][j] 前日卖出后今日不操作

第一天
sell0 = 0
buy0 = -prices[0]
其余交易次数的地位均设为 -inf 代表不可用

class Solution:
    def maxProfit(self, k: int, prices: List[int]) -> int:
        if not prices:
            return 0
        length = len(prices)
        buy = [[0] *(k+1) for _ in range(length)]
        sell = [[0] *(k+1) for _ in range(length)]
        for i in range(1,k+1):
            buy[0][i] = sell[0][i] = float('-inf')
        # set inital value
        sell[0][0] = 0
        buy[0][0] = - prices[0]
        for i in range(1,length):
            # sell[i][0] is always 0
            buy[i][0] = max(buy[i - 1][0], sell[i - 1][0] - prices[i])
            for j in range(1,k+1):
                # iterate
                buy[i][j] = max(buy[i-1][j], sell[i-1][j] - prices[i])
                sell[i][j] = max(buy[i-1][j-1]+prices[i], sell[i-1][j])
        return max(sell[-1])

正文完