最大正方形。在一个由 ‘0’ 和 ‘1’ 组成的二维矩阵内，找到只包含 ‘1’ 的最大正方形，并返回其面积。力扣221。
动态规划。dp[i][j]是正方形右下角的点，值是边长。dp[i][j]依赖左，上，左上。
时间复杂度：O(NM)。
空间复杂度：O(NM)。
代码用golang编写。代码如下：
package main
import "fmt"
func main() {
m := [][]byte{
{1, 1, 1, 0},
{1, 1, 1, 1},
{1, 1, 1, 1},
{1, 1, 1, 1},
}
ret := maximalSquare(m)
fmt.Println(ret)
}
func maximalSquare(m [][]byte) int {
if len(m) == 0 || len(m[0]) == 0 {
return 0
}
N := len(m)
M := len(m[0])
dp := make([][]int, N+1)
for i := 0; i < N+1; i++ {
dp[i] = make([]int, M+1)
}
max := 0
for i := 0; i < N; i++ {
if m[i][0] == 1 {
dp[i][0] = 1
max = 1
}
}
for j := 1; j < M; j++ {
if m[0][j] == 1 {
dp[0][j] = 1
max = 1
}
}
for i := 1; i < N; i++ {
for j := 1; j < M; j++ {
if m[i][j] == 1 {
dp[i][j] = getMin(
getMin(dp[i-1][j],
dp[i][j-1]),
dp[i-1][j-1]) + 1
max = getMax(max, dp[i][j])
}
}
}
return max * max
}
func getMax(a, b int) int {
if a > b {
return a
} else {
return b
}
}
func getMin(a, b int) int {
if a < b {
return a
} else {
return b
}
}执行结果如下：
