【leetcodeブラシ問題】121.株を売買する最良のタイミング(5題まとめ)(python 3)

121.株を売買する最良のタイミング(簡単)
配列が与えられ、そのi番目の要素は、与えられた株のi日目の価格です.
最大1つの取引(株の購入と売却)しか許可されていない場合は、取得できる最大利益を計算するアルゴリズムを設計します.
株を買う前に株を売ってはいけないことに注意してください.

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        # # 1、   ，    ：            （over time）
        # max_p = 0
        # for i in range(len(prices)):
        #     for j in range(i,len(prices)):
        #         tmp = prices[j]-prices[i]
        #         max_p = max(tmp, max_p)
        # return max_p

        # # 2、     ：    ，          (8272ms)
        # max_p = 0
        # for i in range(len(prices)-1):
        #     tmp = max(prices[i+1:])
        #     max_p = max(tmp-prices[i], max_p)
        # return max_p

        # 3、    (44ms)
        #      0      ，1    ;           
        #           0，             
        dp_i_0, dp_i_1 = 0,  float('-inf')
        #         ：    、           
        for i in range(len(prices)):
            #            ，      （     price[i]）；
            #            ，      （     -price[i]）
            dp_i_0=max(dp_i_0, dp_i_1+prices[i])
            dp_i_1=max(dp_i_1, -prices[i])
        return dp_i_0

上題手法3に対して,同手法(3 Dダイナミックプランニング)は以下の問題を類推する.
(1)動的計画方法を理解する:
dp[i][k][0 or 1]0<=i<=n-1,1<=k<=K nが日数,大Kが最大取引数という問題共n× K × 2つの状態は、すべて貧乏で済む.
for 0 <= i < n:     for 1 <= k <= K:         for s in {0, 1}:             dp[i][k][s] = max(buy, sell, rest)
(2)状態遷移方程式
dp[i][k][0]=max(dp[i-1][k][0],dp[i-1][k][1]+prices[i])max(restを選択しsellを選択)
今日私は株を持っていません.2つの可能性があります.昨日持っていなかったか、今日restを選んだので、今日は持っていません.昨日株を持っていたのか、今日はsellになったので、今日は株を持っていません.
dp[i][k][1]=max(dp[i-1][k][1]、dp[i-1][k-1][0]-prices[i])max(rest選択、buy選択)
解釈:今日私は株を持っていて、2つの可能性があります:あるいは私は昨日株を持っていて、それから今日restを選んで、だから私は今日また株を持っています;昨日は持っていなかったのか、今日はbuyを選んだので、今日は株を持っています.
(3)basecase
dp[-1][k][0]=0解釈:iは0から始まるので、i=-1はまだ始まっていないことを意味し、このときの利益は当然0である.dp[-1][k][1]=-infinity解釈:まだ始まっていないときは、株を持つことは不可能であり、負の無限でこのような不可能を表す.dp[i][0][0]=0解釈:kは1から始まるので、k=0は取引がまったく許されないことを意味し、このとき利益は当然0である.dp[i][0][1]=-infinity解釈:取引が許されない場合、株式を保有することは不可能であり、このような不可能を負の無限で表す.
(4)状態遷移方程式のまとめ:
base case: dp[-1][k][0] = dp[i][0][0] = 0 dp[-1][k][1] = dp[i][0][1] = -infinity
状態遷移方程式:dp[i][k][0]=max(dp[i-1][k][0],dp[i-1][k][1]+prices[i])dp[i][k][1]=max(dp[i-1][k][1],dp[i-1][k-1][0]-prices[i])
第1題はk=1
122.株を売買する最良のタイミングII(簡単)k=float(「inf」)
配列が与えられ、そのi番目の要素は、与えられた株のi日目の価格です.
あなたが得られる最大利益を計算するアルゴリズムを設計します.できるだけ多くの取引(株を複数回売買する)を完了することができます.
注意:複数の取引に同時に参加することはできません(再購入前に前の株を売却しなければなりません).

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        dp_i_0, dp_i_1 = 0, float("-inf")
        for i in range(len(prices)):
            tmp = dp_i_0
            dp_i_0 = max(dp_i_0, dp_i_1+prices[i])
            dp_i_1 = max(dp_i_1,tmp-prices[i])
        return dp_i_0

309.最適な株式売買タイミングは冷凍期間(中等)k=float("-inf")+cooldownを含む
i番目の要素がi日目の株価を表す整数配列が与えられます.​
アルゴリズムを設計して最大利益を計算する.以下の制約条件を満たすと、できるだけ多くの取引(株を複数回売買する)を完了することができます.
複数の取引に同時に参加することはできません(再購入する前に前の株を売却しなければなりません).株を売った後、翌日に株を買うことはできません(つまり冷凍期間は1日です).

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        dp_i_0, dp_i_1 = 0, float("-inf")
        dp_i_pre2_0 = 0 #   1 ，       ，                 
        for i in range(len(prices)):
            tmp = dp_i_0 #  i-1       
            dp_i_0 = max(dp_i_0, dp_i_1+prices[i]) #  i       
            dp_i_1 = max(dp_i_1,dp_i_pre2_0-prices[i]) #  i      
            dp_i_pre2_0 = tmp #   i-1           i-2 ，  (i+1)-2       
        return dp_i_0

714.株を売買する最良のタイミングは手数料(中等)k=float(「inf」)with feeを含む
整数配列pricesが与えられ、i番目の要素はi日目の株価を表す.非負の整数feeは、取引株の手数料を表します.
無制限に取引を完了することができますが、取引のたびに手数料を払う必要があります.もしあなたが株を買ったら、それを売る前に株を買うことはできません.
利益の最大値を返します.

class Solution:
    def maxProfit(self, prices: List[int], fee: int) -> int:
        dp_i_0, dp_i_1 = 0, float("-inf")
        for i in range(len(prices)):
            tmp = dp_i_0
            dp_i_0 = max(dp_i_0, dp_i_1+prices[i]-fee)
            dp_i_1 = max(dp_i_1, tmp-prices[i])
        return dp_i_0

123.株の売買に最適なタイミングIII(困難)k=2
配列が与えられ、i番目の要素はi日目の株価である.
あなたが得られる最大利益を計算するアルゴリズムを設計します.最大2つの取引を完了することができます.
注意:複数の取引に同時に参加することはできません(再購入前に前の株を売却しなければなりません).

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        dp_i_1_0, dp_i_1_1 = 0, float("-inf")
        dp_i_2_0, dp_i_2_1 = 0, float("-inf")
        for i in range(len(prices)):
            dp_i_2_0 = max(dp_i_2_0, dp_i_2_1 + prices[i])
            #           ，    ，        k，          k-1
            #          ，         
            dp_i_2_1 = max(dp_i_2_1, dp_i_1_0 - prices[i]) 
            dp_i_1_0 = max(dp_i_1_0, dp_i_1_1 + prices[i])
            dp_i_1_1 = max(dp_i_1_1, dp_i_0_0 - prices[i]) #   dp_i_0_0=0,             
        return dp_i_2_0

大牛原文参考リンク:参考リンク