LeetCodeに挑戦：474. Ones and Zeros（動的計画法）

　今回は、474. Ones and Zeroes　に挑戦します。難易度は Medium となっています。

（問題）
　コンピューターの世界において限られた資源を使って最大の利益を生み出す事を私達は常に追求しています。
　ここで、あなたはそれぞれ m 個の 0 と n 個の1の支配者です。一方で、0 と 1 のみで構成される文字列を持つ配列があります。今あなたのタスクは、指定されたm 個の 0とn 個の 1でつくることのできる文字列の最大数を見つけることです。

　注意：
　1. 指定された 0 と 1 の数は両方とも 100 を超えません。
　2. 指定された文字列配列のサイズは 600 を超えません。

（例1）
Input:  Array = {“10”, “0001”, “111001”, “1”, “0”}, m = 5, n = 3
Output: 4
説明：5つの 0 と3つの 1 を使用することで、合計で4つの文字列を形成できます。それらは、”10″、”0001″、”1″ および “0” です。

（例2）
Input:  Array = {“10”, “0”, “1”}, m = 1, n = 1
Output: 2
説明：”10″ をつくることができますが、その後は何も残りません。”0″ および”1″をつくる方がより良いです。

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

class Solution:
    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
        #(1)
        dp = [[0]*(n+1) for _ in range(m+1)]
        #(2)
        for s in strs:
            #(3)
            zeros = s.count('0')
            ones = s.count('1')
            #(4)
            for x in range(m,-1,-1):
                for y in range(n,-1,-1):
                    #(5)
                    if zeros <=x and ones<=y:
                        #(6)
                        dp[x][y] = max(dp[x][y],dp[x-zeros][y-ones]+1)
        #(7)
        return dp[m][n]

まず (1)の部分で、配列 dp を初期化しています。
この dp は、２次元配列で、dp[ x ] [ y ] に、x 個の “0” と y 個の “1” で、作成可能な文字列の個数をメモしていきます。
よって dp の要素数は、”0″ と “1” それぞれについて、使わない場合もあるため n + 1、m + 1 としています。
また、初期値は 0 です。

(2)の部分から、与えられた文字列の配列 str の要素（文字列）を順にみていきます。

(3)の部分で現在対象とする要素（文字列）に 0 および １が、何個含まれているかを count() 関数を使って、それぞれ zeros、ones という変数名で取得します。

(4)の部分から、与えられる “0” と “1” の個数の範囲内で、現在みている文字列が作成可能かを探索していきます。また、今回は 最も多くの “0” または “1” を使用する場合( x = m, y = n )から、まったく使用しない場合(x = 0 , y = 0 )の方向で探索をしていきます。

現在見ている文字列の “0” の数 zeros と “1” の数が それぞれ x および y 以下であれば、その文字列は作成可能であるため、(5) の if 文で判定を行いTrue であれば、(6) で dp[x][y] を更新します。
その更新の方法は、現在の dp[x][y] か dp[x-zeros][y-ones] に 1を足したもの、のどちらか大きい方です。
dp[x-zeros][y-ones] +1 について詳しく見ていくと、
zeros と ones はそれぞれ、現在みている文字列(s) が持つ “0” と “1” の数でした。そして x と y はそれぞれ、現在使用することのできる “0” と “1” の数です。よって、 x-zeros と y-ones から得られる数は、それぞれ、現在みている文字列を(s)を作成しても、まだ使用することのできる “0” と “1” の数となります。よって、それらの “0” と “1” を使って作成可能な文字列の個数は、dp[x-zeros][y-ones] にメモされているはずですので、 dp[x-zeros][y-ones] に今作成可能となった数である 1 を加えた dp[x-zeros][y-ones] +1 が記述されます。

最後に、dp の最後の要素 dp[m][n] を返して終了です（dp[-1][-1] と書くこともできます）。