LeetCodeに挑戦：DP系問題 Medium (その2)
LeetCodeの方で動的計画法に関するスレッド、Dynamic Programming Questions Thread を見つけましたので、今回はその中にある Medium 問題を解いてみたいと思います。（DP系問題 Medium (その1)は こちら）
139. Word Break
（問題）空でない文字列 s と、空でない単語のリストを持つ辞書 wordDict が与えられます。s を1つ以上の辞書が持つ単語で、スペース区切りとして、分割できるかを判断して下さい。
（例）Input: s = “leetcode”, wordDict = [“leet”, “code”]
Output: ture
説明：”leetcode” は、”leet code” として分割できるため、true を返します。
（解答例）以下に解答例を示します。
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
# (1)
dp = [ 0 for _ in range(len(s)+1)]
dp[0] = 1
# (2)
for i in range(len(s) + 1):
# (3)
if dp[i] == 0:
continue
# (4)
for w in wordDict:
# (5)
if len(w) <= len(s[i:]):
#(6)
if w == s[ i : (i + len(w))]:
dp[i + len(w)] = 1
# (7)
return dp[-1]今回の問題で配列 dp は、文字列 s の各位置までが分割可能かを記録する配列として使用します。分割できる場合は 1 を記入し、できない場合は（初期値である）0 となります。配列 dp の最後 dp[-1] が 1 であれば、その文字列 s は分割可能である事になります。
それでは、上記のコードを個別に見ていきます。
# (1)
dp = [ 0 for _ in range(len(s)+1)]
dp[0] = 1ここでは、配列 dp を初期化しています。dp の要素数は文字列の数 +1としており、先頭 dp[0] をダミーとして、1を代入しています。
# (2)
for i in range(len(s) + 1):
# (3)
if dp[i] == 0:
continue(2)からは、forループで dp を更新していきます。dp の要素数は先述したように、文字列 s の長さ +1 となっています。(3)の if 文では dp[ i ] の値が 0 の場合は、処理を以降の処理を抜けています。これは、文字列 s のこの部分まででは、分割することができない事が確定していますので、以降の処理は不要なためです。
# (4)
for w in wordDict:
# (5)
if len(w) <= len(s[i:]):
#(6)
if w == s[ i : (i + len(w))]:
dp[i + len(w)] = 1(4)からは、dp[ i ] = 1となっていますので、文字列 s の以降の要素も調べて行きます。まず forループで、与えられた wordDict 内のすべての単語を調べます。(5)で、各単語の長さが、文字列 s の以降の文字の長さ以下であることを確認しています。さらに (6)で、各単語が文字列 s の以降の文字と一致するかを調べ、一致した場合は dp に 1を書き込みます。その書き込み先は、現在の位置 i に各単語の長さを足した部分です。
# (7)
return dp[-1]最後に配列 dp の最後の要素を返してプログラムを終了します。
221. Maximal Square
（問題）0 と 1で満たされた 2次元の 2値行列が与えられます。1 のみを含む最大の正方形を見つけ、その面積を返しなさい。
（例）Input:
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
Output: 4
説明：以下で、太字で示す部分の正方形が最大の面積を持つものです。
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
（解答例）以下に解答例を示します。
class Solution:
def maximalSquare(self, matrix: List[List[str]]) -> int:
# (1)
H = len(matrix)
if H == 0:
return 0
W = len(matrix[0])
# (2)
dp = [ 0 for w in range(W)]
mymax = 0
mycandi = 1
# (3)
for h in range(H):
for w in range(W):
if matrix[h][w] == '0':
dp[w] = 0
else:
dp[w] += int(matrix[h][w])
# (4)
mycnt = 0
maxcnt = 0
for ww in range(W):
# (5)
if dp[ww] >= mycandi:
mycnt += 1
if mycnt > maxcnt:
maxcnt = mycnt
else:
mycnt = 0
# (6)
if maxcnt >= mycandi :
mymax = mycandi
mycandi = mymax + 1
# (7)
return (mymax * mymax)今回も、63. Unique Paths II の場合のように、2次元配列の探索結果を、１次元配列に記録しながら解いていきます。
それでは、上記のコードを個別に見ていきます。
# (1)
H = len(matrix)
if H == 0:
return 0
W = len(matrix[0])(1)では、与えられる配列 matrix の行数を H として取得します。また、H = 0 となる場合は、空の配列が与えられたことになるので 0 を返してプログラムを終了します。さらに、 matrix の列数を W として取得します。
# (2)
dp = [ 0 for w in range(W)]
mymax = 0
mycandi = 1(2)では、配列および各変数の宣言と初期化を行います。配列 dp の要素数は marix の列数と同じにします。さらに mymax は答えとなる値（正確には面積ではなく、辺の値です）を格納する変数で、初期値はとりあえず、何もできないとして 0 を代入します。また、mycandi は 、次の目標として 辺 mymax + 1 の正方形が存在するか？を調べたいので、1 を代入しています。
# (3)
for h in range(H):
for w in range(W):
if matrix[h][w] == '0':
dp[w] = 0
else:
dp[w] += int(matrix[h][w])(3)からの 2重のforループで matrix を調べていきます。行 h ごとに、’1′ が続けば dp[w] の値は +1 加算され、’0′ が現れた時点で0に戻します。
例題の場合は、次のように処理されます。
（h） dp[0] dp[1] dp[2] dp[3] dp[4]
0 1 0 1 0 0
1 2 0 2 1 1
2 3 1 3 2 2
3 4 0 0 3 0
各行(h) の処理が終了するごとに、（そこまでで）できる最大の正方形の辺を、以下の処理で、探索していきます。
# (4)
mycnt = 0
maxcnt = 0
for ww in range(W):
# (5)
if dp[ww] >= mycandi:
mycnt += 1
if mycnt > maxcnt:
maxcnt = mycnt
else:
mycnt = 0(4)では、まず2つの変数、mycnt と maxcnt を 0 で初期化します。mycnt は、列方向に mycandi 以上の値が連続して出現している回数を記録するもので、 mycandi 以上の値の連続が途切れた場合は 0 に戻します( (5)の処理 ）。そうすると、for ループの処理が終了した時点で mycnt に格納されている値は、例題では dp[4] の時点での連続数です。しかし、今知りたいのは最大の連続数であるため、maxcnt を用意しておき、最大の連続数を記録しておきます。
# (6)
if maxcnt >= mycandi :
mymax = mycandi
mycandi = mymax + 1(6) では maxcnt が maycandi 以上であれば、目標としていた辺は存在していた事になるので、mycandi に +1 を加算し目標を更新しています。
# (7)
return (mymax * mymax)最後に、求められている答えは面積であったため、 辺 x 辺 の値を返します。
300. Longest Increasing Subsequence
（問題）整数のソートされていない配列が与えられます。最も長い、増加するサブシーケンスの長さを見つけなさい。
（例）Input: [ 10, 9, 2, 5, 3, 7, 101, 18]
Output: 4
説明：最も長い、増加するサブシーケンスは [ 2, 3, 7, 101 ] であるため、長さは4です。
注意：考えられるサブシーケンスは複数存在する場合がありますが、必要なのは長さを返すことだけです。
また、 アルゴリズムは O(n2) の計算量で実行する必要があります。
（解答例）以下に解答例を示します。
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
# (1)
N = len(nums)
if N == 0:
return 0
# (2)
dp = [1 for n in range(N)]
myans = 0
# (3)
for i in range(N):
for j in range(i):
if nums[j] < nums[i]:
dp[i] = max(dp[i], dp[j] + 1)
myans = max(myans, dp[i])
# (4)
return myans
今回の問題では、2つの forループを使って、配列 dp を更新していきます。
それでは、上記のコードを個別に見ていきます。
# (1)
N = len(nums)
if N == 0:
return 0ここでは、与えられる配列 nums の長さを、変数 N として取得しています。よって N = 0 となる場合は、どんなサブシーケンスもつくることはできませんので 0 を返して、プログラムを終了します。
# (2)
dp = [1 for n in range(N)]
myans = 0(2)では、配列 dp を初期化しています。dp の要素数は N とし、また初期値は 1 にしています。これは、数値が1つ存在するのならばサブシーケンスは少なくとも1つはつくる事ができるからです。また変数 myans は最終的な答えを格納するための変数です。
# (3)
for i in range(N):
for j in range(i):
if nums[j] < nums[i]:
dp[i] = max(dp[i], dp[j] + 1)
myans = max(myans, dp[i])(3)からは、2重の forループで dp を更新していきます。外側（変数 i を使用）の forループで、nums を順にみていき、内側（変数 j を使用）の forループで 0（先頭）から i までをみています。そうして、nums[ j ] < nums[ i ] となった場合、つまり増加するサブシーケンスをつくれる場合に dp を更新します。更新の方法は、基本的には dp[ j ] + 1 です。これは、現時点で nums[ i ] よりも値が小さい nums[ j ] が存在しているの、nums[ j ] まで作成可能なサブシーケンスの数 dp[ j ] に nums[ i ] が加わるためです。そして今、得たいのは最長のサブシーケンスですので、絶えず最大値が記録されるように、max(dp[ i ], dp[ j ] + 1)としています。また、後から max(dp) として、答えを取得することもできますが、計算量を減らすために内側の forループを抜けた時点で、myans を最大値で更新しておきます。
# (4)
return myans最後に, myans を返してプログラムを終了します。
“LeetCodeに挑戦：DP系問題 Medium (その2)” に対して1件のコメントがあります。