Dynamic Programming - 221. Maximal Square

221. Maximal Square

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。使用动态规划的思想做，子问题就是对于任意一个值为1的网格，去比较网格上一个格和左边一格和左上角的网格所记录的最大正方形边长。然后当前格的最小正方形边长就等于前面三者最小值加一，所以状态转移方程就是dp[i][j] = min{dp[i-1][j-1], dp[i][j-1], dp[i-1][j]}, dp[i][j]代表了第i行第j列位置为正方形的右下角，所能表示的最大正方形边长。初始条件和边界条件是第一行和第一列。

代码：

go：

func maximalSquare(matrix [][]byte) int {

    if matrix == nil || len(matrix) == 0 || len(matrix[0]) == 0{
        return 0
    }
    
    rows, cols := len(matrix), len(matrix[0])
    maxLen := 0
    dp := make([][]int, rows + 1)
    for i := range dp {
        dp[i] = make([]int, cols + 1)
    }
    
    for i := 1; i < rows + 1; i++ {
        for j := 1; j < cols + 1; j++ {
            if matrix[i-1][j-1] == '1' {
                dp[i][j] = min(min(dp[i-1][j], dp[i][j-1]), dp[i-1][j-1]) + 1
                maxLen = max(maxLen, dp[i][j]) 
            }
        }
    }
    
    return maxLen*maxLen
}

func min(i, j int) int {
    if i < j {
        return i
    }
    return j
}

func max(i, j int) int {
    if i > j {
        return i
    }
    return j
}