力任せのアルゴリズムから動的計画法のアルゴリズムを考える方法について

前提・実現したいこと

最大正方形の面積を求めるプログラムを書いています。
問題としては221. Maximal Squareが同様の内容を扱っており、入力された配列の要素が0なら黒、1なら白とし、白の面積が最大となる場合の１辺の長さを出力します。

#入力
M = [[0, 1, 1, 0, 1], 
    [1, 1, 0, 1, 0], 
    [0, 1, 1, 1, 0], 
    [1, 1, 1, 1, 0], 
    [1, 1, 1, 1, 1], 
    [0, 0, 0, 0, 0]] 

#出力 
3

動的計画法を考える時に再帰関係は以下のように考えています。
i,jは縦と横のindexとして0から始まり、MaxSubSquare(M, i, j)がM[i][j]を左上端とする正方形と考える時、例えば上記の例でMaxSubSquare(M, 3, 3)=3と考えます。
その場合3つの場合分けが可能と考えます。

・MaxSubSquare(M, i, j) = 0 if M[i][j]=0
・MaxSubSquare(M, i, j) = 1 if M[i][j]=1 and M[i+1][j]=0 and M[i][j+1]=0
・MaxSubSquare(M, i, j) = MaxSubSquare(M, i, j) + 1 if M[i][j]=1 and M[i+1][j]=1 and M[i][j+1]=1 and M[i+1][j+1]=1

発生している問題・エラーメッセージ

動的計画法のアルゴリズムによるプログラムを実行したところ、エラーが出力されず、以下の出力のみでした。
求めたいのは今回の入力の場合、3ですが、１人では現行のコードをどのように修正すべきかわかりません。
アドバイスや意見をいただきたいです。

$ python dpsquare.py
None

該当のソースコード

力任せのアルゴリズムは、参考記事の出力を少し変えて実行し、正しい出力を得られました。

力任せのアルゴリズムによるプログラム

python
1# Python3 code for Maximum size 
2# square sub-matrix with all 1s 
3
4def MaxSubSquare(M): 
5    R = len(M) # no. of rows in M[][] 
6    C = len(M[0]) # no. of columns in M[][] 
7
8    S = [[0 for k in range(C)] for l in range(R)] 
9    # here we have set the first row and column of S[][] 
10
11    # Construct other entries 
12    for i in range(1, R): 
13        for j in range(1, C): 
14            if (M[i][j] == 1): 
15                S[i][j] = min(S[i][j-1], S[i-1][j], 
16                            S[i-1][j-1]) + 1
17            else: 
18                S[i][j] = 0
19    
20    # Find the maximum entry and 
21    # indices of maximum entry in S[][] 
22    max_of_s = S[0][0] 
23    max_i = 0
24    max_j = 0
25    for i in range(R): 
26        for j in range(C): 
27            if (max_of_s < S[i][j]): 
28                max_of_s = S[i][j] 
29                max_i = i 
30                max_j = j 
31
32    print("Maximum size sub-matrix is: ") 
33
34    count = 0
35    for i in range(max_i, max_i - max_of_s, -1): 
36        count += 1
37    print(count)
38
39# Driver Program 
40M = [[0, 1, 1, 0, 1], 
41    [1, 1, 0, 1, 0], 
42    [0, 1, 1, 1, 0], 
43    [1, 1, 1, 1, 0], 
44    [1, 1, 1, 1, 1], 
45    [0, 0, 0, 0, 0]] 
46
47printMaxSubSquare(M) 
48#出力 3

動的計画法のアルゴリズムによるプログラム

python
1def dpsquare(M, i, j):
2	max = 0
3	if M[i][j]== 0:
4		return 0
5	elif M[i][j]==1 and M[i+1][j]==1 and M[i][j+1]==1 and M[i+1][j+1]==1:
6		return MaxSubSquare(M, i, j) + 1
7	elif M[i][j]==1 and M[i+1][j]==0 and M[i][j+1]==0:
8		return 1
9
10M = [[0, 1, 1, 0, 1], 
11    [1, 1, 0, 1, 0], 
12    [0, 1, 1, 1, 0], 
13    [1, 1, 1, 1, 0], 
14    [1, 1, 1, 1, 1], 
15    [0, 0, 0, 0, 0]] 
16
17i = 3
18j = 3
19print(dpsquare(M, i, j))

補足情報（FW/ツールのバージョンなど）

python 3.6

行動規範の内容に同意します

回答1件

ベストアンサー

提示コードだと以下のような場合にどのif文にも到達せずNoneが返ります。

[1,1]
[1,0]

まず第一歩として修正するとしたら以下のような感じでしょうか。

Python
1def dpsquare(M, i, j):
2    max = 0
3    if M[i][j]== 0:
4        return 0
5    elif M[i][j]==1 and M[i+1][j]==1 and M[i][j+1]==1 and M[i+1][j+1]==1:
6        return dpsquare(M, i+1, j+1) + 1 # 次の位置
7    return 1
8
9M =[[0, 1, 1, 0, 1], 
10    [1, 1, 0, 1, 0], 
11    [0, 1, 1, 1, 0], 
12    [1, 1, 1, 1, 0], 
13    [1, 1, 1, 1, 1], 
14    [0, 0, 0, 0, 0]] 
15
16i,j = 2,1 # ２行１列目
17print(dpsquare(M, i, j)) # 3