# 9-lines Python DP solution with explaination

• ``````def maximalSquare(self, matrix):
dp, maxArea = [[0 for _1_ in range(len(matrix[0]))] for ___ in range(len(matrix))], 0
for i in xrange(0, len(matrix)):
for j in xrange(0, len(matrix[0])):
if i == 0 or j == 0:
dp[i][j] = int(matrix[i][j])
elif int(matrix[i][j]) == 1:
dp[i][j] = min(dp[i - 1][j - 1], dp[i][j - 1], dp[i - 1][j]) + 1
maxArea = max(maxArea, dp[i][j])
return maxArea*maxArea
``````

We define dp[i][j] the maximal ending at position (i, j). Thus, current state (`dp[i][j]`)depends on left (`dp[i][j - 1]`), up (`dp[i - 1][j]`), and left-up's (`dp[i - 1][j - 1]`) states. The current state equals to the minimum of these three states plus `matrix[i][j]` because any smaller value will lead to a smaller square (holes in somewhere). I use `maxArea` to track the maximal square. When `matrix[i][j] == '0'`, the maximal square ending at position (i, j) is obviously 0.

Recurrence relation:

For `matrix[i][j] == 1`, `dp[i][j] = min(dp[i - 1][j - 1], dp[i][j - 1], dp[i - 1][j]) + int(matrix[i][j])`.

For `matrix[i][j] == 0`, `dp[i][j] = 0`

• Thanks for your wonderful explanation!

• left-up's (`dp[i- 1][j]`) state should be `dp[i-1][j-1]`

• Fixed, I have revised it.

• easy understanding solution. THx

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.