【leetcodeノート】Python実現309.Best Time to Buy and Sell Stock with Cooldown

タイトルの説明
Say you have an array for which the ith element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times) with the following restrictions:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
After you sell your stock, you cannot buy stock on next day. (ie, cooldown 1 day)
Example:
Input: [1,2,3,0,2] Output: 3 Explanation: transactions = [buy, sell, cooldown, buy, sell]
テーマの大意
一連の株式取引価格を提示し、株式取引の原則は先に買ってから売らなければならず、購入する前に少なくとも1日休まなければならない.最後に得ることができる最大の収益を求めます.
解題方法
ダイナミックプランニング
この問題と「leetcodeノート」Python実現714.Best Time to Buy and Sell Stock with Transaction Feeが似ています.問題の作成方法は2つの配列を使用しています.
Cash[i]この日終了手持ち株式がない場合、既に獲得した最大収益hold[i]この日終了手持ち株式の場合、すでに獲得した最大収益
状態遷移方程式:
cash[i]では、最大利益は2つの可能性があります.1つは、今日は昨日の株を持っていない状態と同じように動作していないことです.2つは、今日株を売ったことです.そのため、状態移行方程式は以下の通りです.
max(昨日は株の収益がなく、昨日は株の収益があった+今日は株の収益があった)

cash[i] = max(cash[i - 1], hold[i - 1] + prices[i])

hold[i]では、最大利益は2つの可能性があります.1つは、今日は昨日の持株状態と同じように動作していないことです.2つは、一昨日株を売って、今日株を買ったことです.cooldownは翌日しか取引できないので、今日株を買うのは一昨日の状態にさかのぼります.状態遷移方程式は次のとおりです.
max(昨日株を手にした収益、一昨日株を売った収益-今日株の価格).

hold[i] = max(hold[i - 1], cash[i - 2] - prices[i])。

最終的に我々が要求した結果はcash[n-1]であり,最終日の終了時に株を手にしなかった場合の最大利益を示した.
このアルゴリズムの空間的複雑さはO(n)であるが,cash[i]は前項のみ,hold[i]は前項2のみに依存するため,O(1)に最適化でき,具体的には第2のコード実装を参照できる.
コードは次のとおりです.
時間的複雑度はO(n),空間的複雑度はO(n)である.

class Solution:
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        if not prices: return 0
        cash = [0] * len(prices)
        hold = [0] * len(prices)
        hold[0] = -prices[0]
        for i in range(1, len(prices)):
            cash[i] = max(cash[i - 1], hold[i - 1] + prices[i])
            hold[i] = max(hold[i - 1], (cash[i - 2] if i >= 2 else 0) - prices[i])
        return cash[-1]

空間複雑度O(1)

class Solution:
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        if not prices: return 0
        prev_cash = 0
        curr_cash = 0
        hold = -prices[0]
        for i in range(1, len(prices)):
            temp = curr_cash
            curr_cash = max(curr_cash, hold + prices[i])
            hold = max(hold, (prev_cash if i >= 2 else 0) - prices[i])
            prev_cash = temp
        return curr_cash

変換元:https://blog.csdn.net/fuxuemingzhu/article/details/82656899参照先:https://soulmachine.gitbooks.io/algorithm-essentials/java/dp/best-time-to-buy-and-sell-stock-with-cooldown.html