LeetCodeに挑戦：DP系問題 Easy

　先日のAtCoder ABC153では動的計画法を使う問題をうまく解けませんでした。そんな中で、ちょうどLeetCodeの方で動的計画法に関するスレッド、Dynamic Programming Questions Thread を見つけましたので、今回はその中にある EASY 問題を解いてみたいと思います。

121. Best time to buy and sell stock

（問題）i 番目の要素が、i 日目のある１つの株式の価格でとなる配列 (prices) があるとします。任意の日に1株だけを購入して、任意の日にその1株を売却する場合、最大の利益を見つけるためのアルゴリズムを設計して下さい。ただし購入する前に株を売却することはできません。また利益が 0 よりも小さくなる場合は 0 を返して下さい。

（例）Input: [7,1,5,3,6,4]
　　　Output: 5
　　　説明：2日目に購入し（価格= 1）、5日目に販売（価格= 6）すれば、利益 = 6 – 1 = 5 が最大となります。
              　販売価格は購入価格よりも大きくする必要があるため、7 – 1 = 6 とはなりません。

（解答例）解答例を以下に示します。

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        # (1)
        if not prices:
            return 0
        # (2)
        buy = prices[0]
        ans = 0 
        # (3)
        for p in prices:
            #(4)
            if p > buy:
                ans = max(ans, p - buy)
            #(5)
            else:
                buy = p
        #(6)
        return ans

各部分について見ていきます。

 　　　　# (1)
        if not prices:
            return 0

(1)については、LeetCodeではよくあるやつで、国内のコンテストではあまり意識することはありませんが、空の配列が与えられた場合の処理です。

 　　　　# (2)
        buy = prices[0]
        ans = 0 

(2)の部分では、変数の初期化を行います。
buy は、購入候補の株を入れるための変数で、初期値は配列の先頭 prices[0] としています。
また、ans は 答えを入れるための変数で、初期値は 0 としています。これは、問題中に利益が 0 よりも小さくなる場合は 0 を返すように指定されているため、0 が答えの取り得る範囲の最小値となるからです。

        # (3)
        for p in prices:            
            #(4)
            if p > buy:
                ans = max(ans, p - buy)
            #(5)
            else:
                buy = p

(3)〜(5)の部分が、DPで解いている部分です。
(3)のforループで、配列のすべての要素を見ていきます。
(4)の部分からの if 文で、
まず、現在参照している配列の要素 p が、購入候補であるbuyより大きい場合のみ処理を行います。これは株が値上がりしている場合を想定した処理です。また処理内容は、答え ans を これまでの ans か、今まさに計算している p – buy のどちらか大きいものに更新するというものです。
次に、現在参照している配列の要素 p が、購入候補であるbuy 以下の場合は、購入候補を p に入れ替える処理です。これは、株の購入価格が低いほど、利益を得るのには有利ですので、そのような処理を行います。

　　　　　#(6)
         return ans

for ループを抜けた後、すなわち配列の全要素を見終わった後、答えを返して終了します。

あらためて、本プログラムで例題で、変数がどのように変化していくかを確認します。

prices の要素の中の最小値 1（prices[1] の値）をしっかりと buy で保持できている事が、よく分かりますね。

198. House Robber

（問題）あなたは通りに沿った家々から盗みを計画している泥棒です。各家には、ある一定量のお金が隠されており、また各家には、ある条件で作動するセキュリティシステムがあります。その条件とは、２つの隣接する家が同じ夜に侵入された場合で、その場合自動的に警察に通報されます。
　各家に隠されている金額を示す、非負の整数のリストが与えられるので、警察に通報されずに今夜あなたが盗むことのできる最大金額を返して下さい。

（例）Input: [1,2,3,1]
　　　Output: 4
　　　説明：1件目から盗み（金額= 1）、3件目から盗む（金額= 3）すれば、合計金額 = 1 + 3 = 4 が最大となります。

（解答例）解答例を以下に示します。

class Solution:
    def rob(self, nums: List[int]) -> int:
        
        #(1)
        pre, cur = 0, 0
        
        #(2)
        for n in nums:
            #(3)
            pre, cur = cur, max(pre + n, cur)
        #(4)    
        return cur

今回の問題では、隣接する要素は加算することができません。よって2つの変数 (pre と cur)を用意し、足すことのできる変数(pre) と　足すことのできない変数(cur)のどちらが大きいかを比較しながら、配列を見ていくことになります。

各部分について見ていきます。

 　　　　# (1)
        pre, cur = 0, 0

(1)で、2つの変数 pre, cur を 0で初期化します。今回は最大値を求める問題なので、最小値で初期化しています。

各部分について見ていきます。

 　　　　# (2)
        for n in nums:
            #(3)
            pre, cur = cur, max(pre + n, cur) 

(2)のforループで、配列のすべての要素を見ていきます。
(3)の部分では、
まず pre に cur をそのまま代入しています。これは、現在見ている要素を絶対に足さない場合という処理になります。この処理により、pre は前の要素を足していないので、現在見ている要素をpreに足した場合の検討ができるようになります。
次に、curに対しては、pre に対して、現在見ている要素を足した場合と、足さない場合の大きい方を代入しています。この処理により、cur は絶えず、現在見ている要素までの、最大値が代入されていることになります。

　　　　　#(4)
         return cur

for ループを抜けた後、すなわち配列の全要素を見終わった後、答えを返して終了します。

あらためて、本プログラムで例題で、変数がどのように変化していくかを確認します。

cur で各要素を参照した時、それまでの最大値を保持できている事が、よく分かりますね。

256. Paint House

※有料問題なので、私は見ることができませんでした。。