LeetCodeに挑戦：DP系問題 Medium (その1)

LeetCodeの方で動的計画法に関するスレッド、Dynamic Programming Questions Thread を見つけましたので、今回はその中にある Medium 問題を解いてみたいと思います。（Easy 問題はこちら）

64. Minimum Path Sum

（問題）非負の数値でみたさえた m x n グリッドが与えられます。左上から右下へ到達する経路で、数値の合計が最小となるものを見つけて下さい。
注：下または右にしか移動できません。

（例）Input: [
　　　　　　　[1, 3, 1],
　　　　　　　[1, 5, 1],
　　　　　　　[4, 2, 1] ]
Output: 7
　　　説明： 1→3→1→1→1 と通る経路の合計 7 が最小値となります。

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

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        
        # (1) 
        m = len(grid)
        n = len(grid[0])
        if m == 0:
            return 0
        # (2)
        dp = [0 for _ in range(n)]
        dp[0] = grid[0][0]
        # (3)
        for i in range(1,n):
            dp[i] = dp[i-1] + grid[0][i]
        # (4) 
        for i in range(1,m):
            dp[0] += grid[i][0]
            # (5)
            for j in range(1,n):
                dp[j] = min(dp[j-1], dp[j]) + grid[i][j]
                
        # (6)        
        return(dp[-1])

ほぼ、上記の 63. Unique Path Ⅱと同じような問題で、今回も2次元配列が与えられ、左上をスタート地点とし、下か右かの移動で、右下のゴールを目指します。今回はさらに、各グリッドに数値があり、その数値の合計が少ないように経路を選んでいく必要があります。

それでは、上記のコードを個別に見ていきます。

        # (1) 
        m = len(grid)
        n = len(grid[0])
        if m == 0:
            return 0

(1)では、与えられる２次元配列 grid の行数を m、列数を n として取得しています。また行数が0の場合は0を返 LeetCode のｱﾚな処理を書いています。

        # (2)
        dp = [0 for _ in range(n)]
        dp[0] = grid[0][0]

(2)では、そのグリッドに到達するまでの数値の合計を記録する１次元配列 dp を生成して、0 で初期化しています。今回は gird の列数を要素数として持つ、１次元配列です。 また今回もスタート地点は左上と定められているので、dp[0] に grid[0][0] を代入しています。

        # (3)
        for i in range(1,n):
            dp[i] = dp[i-1] + grid[0][i]

(3)では、まず最初に grid の1行目（grid[0]）のみを見ていきます。また、dp の先頭の要素(dp[0]) は(2)の部分ですでに、計算していますので、 for ループで指定する range は　1から n（列の数）としています。具体的な計算は、進路である右方向に、各グリッドに書かれている数値を加算していくものです。

        # (4) 
        for i in range(1,m):
            dp[0] += grid[i][0]
            # (5)
            for j in range(1,n):
                dp[j] = min(dp[j-1], dp[j]) + grid[i][j]  

(4)からは、下方向に計算をすすめていきます。(3)において、 grid の1行目（grid[0]) の処理は終えていまので、 for ループで指定する range は　1から m（行の数）としています。
まず、最初に（各）行の左端の要素を dp[0] += grid[i][0] と処理します。これは、dp の値は上の行での数値の合計が記録された状態からはじまりますので、 これから見ていくグリッドの数値の合計は、dp の値にそのまま当該グリッドの値を足せば良いことになります。
つづいて、右方向（各列）を計算していきます。ここでも、当該グリッドの値を足す処理自体は変わらないのですが、問題は何に足すか？とい部分です。左端の行については、基本的に上からしかアプローチできませんので、先の dp[0] += grid[i][0] で良かった訳ですが、2行目以降は左からのアプローチもあり得ます。そして、今回の問題は、合計が最小となる経路を選ぶことが目的なので、 min(dp[j-1], dp[j]) + grid[i][j] として、左側と上側の数値の小さい方を選ぶという処理をしています。この部分が、いわゆる漸化式ということになろうかと思います。

        # (6)        
        return(dp[-1])

最後に、今回も右下がゴールと定められているので、dp の最後の要素を返して終了です。

91. Decode Ways

（問題）A〜Zの文字を含むメッセージは、次のマッピングを使用して数字にエンコードされます。
　　　 ‘A’ -> 1
　　　 ‘B’ -> 2
　　　 …
　　　 ‘Z’ -> 26
　　　数字のみを含む、空でない文字列が与えられた場合、それをデコードする方法の総数を返して下さい。

（例）Input: “226”
　　 Output: 3
説明： ２ と 26と捉えた場合は”BZ”、 ２2 と 6と捉えた場合は”VF” (22 6)、そして 2 と 2 と 6 と捉えた場合は “BBF” とデコードすることができ、総数は 3 となります。

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

class Solution:
    def numDecodings(self, s: str) -> int:
        # (1)
        n = len(s)
        if n == 0 or s[0] == '0':
            return 0
        # (2)
        dp = [0 for _ in range(n + 1)] 
        dp[0] = 1 
        dp[1] = 1
        #(3)
        for i in range(2, n + 1):
            # (4)
            first = int(s[i-1])
            second = int(s[i-2:i])
            # (5)
            if first >= 1 and first <= 9:
                dp[i] += dp[i - 1]
            #(6)
            if second >= 10 and second <= 26:
                dp[i] += dp[i - 2]
        #(7)
        return dp[n]

それでは、上記のコードを個別に見ていきます。

        # (1)
        n = len(s)
        if n == 0 or s[0] == '0':
            return 0

(1)では、与えられる文字列 s の長さを n として取得します。 n = 0 の場合は0を返すLeetCode のｱﾚな処理を書いています。さらに、文字列の先頭が “0” になっている場合は、デコードする方法がありませんので、 0 を返して、プログラムを終了させています。

# (2)
dp = [0 for _ in range(n + 1)]
dp[0] = 1
dp[1] = 1

        # (2)
        dp = [0 for _ in range(n + 1)] 
        dp[0] = 1 
        dp[1] = 1

(2)では、デコードできる総数を記録する配列 dp を初期化しています。dp の長さ（len(dp)）は 文字列 s の長さ n よりも1つ多くとっています。これは s[ i ] までの文字を用いてデコードすることができる総数を dp[ i+1] に記録することにしているためです。
また、dp [ 0 ] = 1 は、ダミーで動的計画法において一般的に使われるテクニック（らしい…）です。さらに、dp [ 1 ] = 1 については、s[ 0 ] における、デコード可能な数を記録している訳ですが、(1)の部分で s [ 0 ] = “0” となる可能性は排除していますので、s[ 0 ] は “1”〜”9″ のいずれかとなり、デコード可能な数は 1であると限定することができます。

        #(3)
        for i in range(2, n + 1):
            # (4)
            first = int(s[i-1])
            second = int(s[i-2:i])

(3)からは、文字列 s を forループで順にみていきます。その時 range は 2 から始めています。これは、(4)で、first と second という変数を用いているためです。first は現在注目している文字を、second は first とさらにもう１つ前の文字でできる、2文字を定義して（数値に変換して）います。よって、 out of range を防ぐために、 range は 2 から始めています。forループで使用する i は、dp を基準としており、dp[ i ] と s[ i-1] が対応関係にあることに注意して下さい。また、なぜfirst と second という変数を用いるかは、以降で説明します。

            # (5)
            if first >= 1 and first <= 9:
                dp[i] += dp[i - 1]
　　　　　　　#(6)
            if second >= 10 and second <= 26:
                dp[i] += dp[i - 2]

(5)、(6)で実際にfirst と second という変数を用いて判定分で処理を行います。その内容を s = “1225”を例に、説明してみます。
　今、i = 4　とすれば、
　first = int(s[ i-1 ]) = 5
　second = int(s[ i – 2 : i ]) = 25 となります。

first に着目した場合、122と5は、どちらもデコード可能です。一方で、仮に first = 0 とすれば、122と0では、0 がデコードできないため、122で可能であったデコードの総数を活かすことができなくなります。よって first が 1〜9 の間の数字であることが重要になります。
second の場合も、基本的には同様の考え方で、12と25はちらもデコード可能です。一方で、仮に first = 9 とすれば、second = 29 となり、12と29では29がデコードできないため、12 でできていたデコードの総数を活かすことができなくなります。よって second が 10〜26 の間の数字であることが重要になります。

         #(7)
         return dp[n]

　　　#(7)
return dp[n]

最後に、配列 dp に記録されている、最後の要素を返します。



この問題から、一気に難しくなった気がします。。感覚的には分かるのですが、いざ文として説明してみると簡潔に書くのは非常に難しいです。より、初学者にも分かりやすい説明方法があればぜひ教えて下さい。

また、続きは LeetCodeに挑戦：DP系問題 Medium (その2) へ。