こんにちは
今回の学びは
最大求める！で二次元配列だったら、DPでしょ。
なぜ、これがすり抜ける？だって、現在の状態から正方形を作れなかったんだもん。。。だったら＝＞
-> もっとも簡単なパターン2x2で考えてみるkと。そして、基本はそれが使い魔せると信じること
（時間配分は5分問題理解=restate&clarify 10分検討multip-sol, analysis, reasons 10分実装 20分振り返り の一文45分構成)をできればgoogle docで笑&真剣。
終始、わからないことは声にだして、明確にしていきましょう。
１，まずは入出力をしっかりおさえましょう。（問題を自分の言葉で復唱すること、わからないことをクリアにすると、前提も声にだすこと）
２，いくつかのソリューションを声にだして出してみましょう。（もちろんtime complexit, space complexityの分析や理由を付け加えて）
３，どれでいくか、一緒に決定しましょう。（理由付きでね、よろしく）
timespace analysis (時間とスペースの分析）は 〇〇です
場合によっては、pseudocode（擬似コード）をかいてみてもよい。
Given a 2D binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area.
Example: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
Q: Size of the input?
Q: expected runtime?
C: return max area
Solutions
- loop(m) -> loop(n) validate
全然validateの方法がわからんぞ。10分経過
人間だったらどうするか？
・視点をきめる、縦横、それぞれ最大はいくつか？
例えば(1, 2)のポイントの横は3縦は2である。その情報をもとに
それらがすべて1か確認する。
横縦を一個づつ増やして、成立するか確認するwhile 1続く * O(M)
def is_range(matrix, i, j):
N = len(matrix)
M = len(matrix[0])
if i < 0 or i >= N: return False
if j < 0 or j >= M: return False
return True
def validate(matrix, x, y, length):
for n in range(length+1):
i, j = x + n, y + n
if matrix[i][j] != 1:
return False
return True
def get_max_square(matrix, x, y):
counter = 0
i, j = x, y
while is_range(i, j) and matrix[i][j] == 1:
if validate(matrix, i, j, counter)
counter += 1
i += 1
j += 1
return counter ** 2
def solve(matrix: List[List[int]]) -> int:
N = len(matrix)
M = len(matrix[0])
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
とけなかったので回答みたらdpつかってたのがまず目にはいったので
dpでいきましょう。
dp[i][j]はi,jが1で最大のmax areaとすると
dp[i][j] = dp[1][i-1][j-1]
#それでも思いつかないので
をみた。
初見、わからない。
最大求める！で二次元配列だったら、DPでしょ。
なぜ、これがすり抜ける？だって、現在の状態から正方形を作れなかったんだもん。。。
2x2まあではできるよ。
そのあとの3x3とがむずくね？
1
11
11
111 111
111 122
111 111
111 122
111 123
奇跡やん、こんなん。
状態はi, jが{0, 1}
価値関数はf(i, j)まできた時の, max area
方策関数は上、左上、左のminに対して、i,jが1なら +1 そうでないなら0
-> もっとも簡単なパターン2x2で考えてみるkと。そして、基本はそれが使い魔せると信じること
100011
101111
111011
011001
1111
1111
1111
４、実装しましょう。
できませんでした。
最初のボツ実装はこちら。
class Solution:
def maximalSquare(self, matrix: List[List[str]]) -> int:
def is_range(matrix, i, j):
N = len(matrix)
M = len(matrix[0])
if i < 0 or i >= N: return False
if j < 0 or j >= M: return False
return True
def validate(matrix, h, w, length):
for n in range(length):
for m in range(length):
i, j = h + n, w + m
if matrix[i][j] != 1:
return False
return True
def get_max_square(matrix, x, y):
counter = 0
i, j = x, y
while is_range(matrix, i, j) and matrix[i][j] == 1:
if validate(matrix, x, y, counter):
counter += 1
i += 1
j += 1
return counter ** 2
def solve(matrix: List[List[int]]) -> int:
N = len(matrix)
if N == 0: return 0
M = len(matrix[0])
maxi = 0
for i in range(N):
for j in range(M):
local = get_max_square(matrix, i, j)
maxi = max(local, maxi)
return maxi
matrix2 = [list(map(int, row)) for row in matrix]
return solve(matrix2)
回答をみる。
そのあと、
それぞれのi,jまでの範囲ででの最大をだしていく。 つまりdp[i][j]は範囲を右下をi,jとした時の最大面積は？という価値関数になる。 状態は、0か1のどちらか 0の場合は、0となる。これまでの最高を引鶴と、うまく行かないのは自明。 だから1の場合は、上、左、左上の３店のminに1を加える とここまでいうと dp[i][j]は範囲を右下をi,jとした時、右下を含む範囲全体の最大面積は？という価値関数になる。 なので、毎回dp[i][j]を計算していって、maxを更新する作業O(1)が必要です
class Solution:
def maximalSquare(self, matrix: List[List[str]]) -> int:
"""
それぞれのi,jまでの範囲ででの最大をだしていく。
つまりdp[i][j]は範囲を右下をi,jとした時の最大面積は？という価値関数になる。
状態は、0か1のどちらか
0の場合は、0となる。これまでの最高を引鶴と、うまく行かないのは自明。
だから1の場合は、上、左、左上の３店のminに1を加える
とここまでいうと
dp[i][j]は範囲を右下をi,jとした時、右下を含む範囲全体の最大面積は？という価値関数になる。
なので、毎回dp[i][j]を計算していって、maxを更新する作業O(1)が必要です
"""
n = len(matrix)
if n == 0: return 0
m = len(matrix[0])
dp = [[0] * m for _ in range(n)]
maxi = 0
for i in range(n):
dp[i][0] = int(matrix[i][0])
maxi = max(dp[i][0], maxi)
for j in range(m):
dp[0][j] = int(matrix[0][j])
maxi = max(dp[0][j], maxi)
for i in range(1, n):
for j in range(1, m):
dp[i][j] = 0 if matrix[i][j] == "0" else min(
dp[i-1][j-1],
dp[i][j-1],
dp[i-1][j]
) + 1
maxi = max(dp[i][j]**2, maxi)
return maxi
５、エッジケースとサンプルテストを忘れずに！
ついでにtopdownでも。これだとTLEエラーになるので、
class Solution: # topdown
def maximalSquare(self, matrix: List[List[str]]) -> int:
n = len(matrix)
if n == 0: return 0
m = len(matrix[0])
maxi = 0
def square_matrix(matrix, i, j):
if i >= n or j >= m: return 0
if matrix[i][j] == "0": return 0
return 1 + min(
square_matrix(matrix, i+1, j),
square_matrix(matrix, i , j+1),
square_matrix(matrix, i+1, j+1),
)
for i in range(0, n):
for j in range(0, m):
local = square_matrix(matrix, i, j)
maxi = max(local**2, maxi)
return maxi
キャッシュをいれてみましょうー
あら不思議、@lru_cache(maxsize=None)をいれただけでTLEがクリアされて通りましたよ！
matrix, listはhashableではないので、インターフェースをすこし替えてますが。（理由はpythonのしくみで書いてます。）
from functools import lru_cache
class Solution: # topdown
def maximalSquare(self, matrix: List[List[str]]) -> int:
n = len(matrix)
if n == 0: return 0
m = len(matrix[0])
maxi = 0
@lru_cache(maxsize=None)
def square_matrix(i, j):
if i >= n or j >= m: return 0
if matrix[i][j] == "0": return 0
return 1 + min(
square_matrix(i+1, j),
square_matrix(i , j+1),
square_matrix(i+1, j+1),
)
for i in range(0, n):
for j in range(0, m):
local = square_matrix(i, j)
maxi = max(local**2, maxi)
return maxi
振り返り
「次のこの問題を解くばあい知っていればよい一つの事実とは？」
まとめ
最大求める！で二次元配列だったら、DPでしょ。
なぜ、これがすり抜ける？だって、現在の状態から正方形を作れなかったんだもん。。。だったら＝＞
-> もっとも簡単なパターン2x2で考えてみるkと。そして、基本はそれが使い魔せると信じること
以上です