Dynamic Programming - 221. Maximal Square

ppxai

发布于 2020-09-23 17:25:13

30900

代码可运行

文章被收录于专栏：皮皮星球皮皮星球

运行总次数：0

代码可运行

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
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2019年08月08日，如有侵权请联系 cloudcommunity@tencent.com 删除