动态规划-最大的正方形面积

本文共391个字,预计阅读时间需要1分钟。

题目表述

Given a 2D binary matrix filled with 0’s and 1’s, find the largest square containing only 1’s and return its area.

For example, given the following matrix:

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

Return 4.

思路

使用动态规划来求解,算法时间复杂度O(n^2)。

dp[i][j] : 以(i, j)为右下角的面积最大的正方形的边长。

初始条件:最上面一行,最左边一列,可以直接得到dp值。

更新公式:matrix[i][j] == ‘0’ – > dp[i][j] = 0

        matrix[i][j] == ‘1’ – > dp[i][j] = min(dp[i – 1][j], dp[i – 1][j – 1], dp[i][j – 1]) + 1

 

代码

 

读者评分
[评分人数: 0 平均分: 0]

评论