一, 输入一个二维01矩阵,判断矩阵中全为1的正方形的最大边长
1, 问题描述
输入一个二维01矩阵,判断矩阵中全为1的正方形的最大边长
2, 输入:
0 1 1 0 1 0 1 1 1 0 1 1 0 1 1 1 1 0 0 0 0 1 0 1 1 1 0 0 0 0
输出:
2
3, 算法思想(动态规划):
对于在矩阵内搜索正方形或长方形的题型,一种常见的做法是定义一个二维 dp 数组,其中
dp[i][j] 表示满足题目条件的、以 (i, j) 为右下角的正方形或者长方形的属性。对于本题,则表示以 (i, j) 为右下角的全由 1 构成的最大正方形边长,如果当前位置是 0,那么 dp[i][j] 即为 0;
状态转移方程:
dp[i][j] = min(dp[i-1][j-1], min(dp[i][j-1], dp[i-1][j])) + 1
代码实现
class Solution(object): def getmax(self, lists): if lists == [] or not lists: return 0 row = len(lists) col = len(lists[0]) res = 0 dp = [[0 for i in range(col)] for j in range(row)] for i in range(row): for j in range(col): if i == 0 or j == 0: if lists[i][j] == 1: dp[i][j] = 1 res = 1 for i in range(row): for j in range(col): if lists[i][j] == 1: mins = min(dp[i-1][j], dp[i][j-1]) dp[i][j] = min(dp[i-1][j-1], mins) + 1 res = max(res, dp[i][j]) return res