// 我还是感觉吧，很多时候dp光是为了初始化就得遍历一遍数组。
// 我们可以依靠这个特点设计dp
可以使用动态规划降低时间复杂度。我们用 dp(i, j)dp(i,j) 表示以 (i, j)(i,j) 为右下角，且只包含 11 的正方形的边长最大值。如果我们能计算出所有 dp(i, j)dp(i,j) 的值，那么其中的最大值即为矩阵中只包含 11 的正方形的边长最大值，其平方即为最大正方形的面积。
那么如何计算 dpdp 中的每个元素值呢？对于每个位置 (i, j)(i,j)，检查在矩阵中该位置的值：
如果该位置的值是 00，则 dp(i, j) = 0dp(i,j)=0，因为当前位置不可能在由 11 组成的正方形中；
如果该位置的值是 11，则 dp(i, j)dp(i,j) 的值由其上方、左方和左上方的三个相邻位置的 dpdp 值决定。具体而言，当前位置的元素值等于三个相邻位置的元素中的最小值加 11，状态转移方程如下：
dp(i, j)=min(dp(i−1, j), dp(i−1, j−1), dp(i, j−1))+1
dp(i,j)=min(dp(i−1,j),dp(i−1,j−1),dp(i,j−1))+1
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/maximal-square/solution/zui-da-zheng-fang-xing-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
func maximalSquare(matrix [][]byte) int {
dp := make([][]int, len(matrix))
maxSide := 0
for i := 0; i < len(matrix); i++ {
dp[i] = make([]int, len(matrix[i]))
for j := 0; j < len(matrix[i]); j++ {
dp[i][j] = int(matrix[i][j] - '0')
if dp[i][j] == 1 {
maxSide = 1
}
}
}
for i := 1; i < len(matrix); i++ {
for j := 1; j < len(matrix[i]); j++ {
if dp[i][j] == 1 {
dp[i][j] = min(min(dp[i-1][j], dp[i][j-1]), dp[i-1][j-1]) + 1
if dp[i][j] > maxSide {
maxSide = dp[i][j]
}
}
}
}
return maxSide * maxSide
}
func min(x, y int) int {
if x < y {
return x
}
return y
}
