问题描述
Given a 2D binary matrix filled with 0‘s and 1‘s, find the largest square containing all 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.
解决思路
动态规划。
程序
public class Solution {
public int maximalSquare(char[][] matrix) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return 0;
}
int n = matrix.length, m = matrix[0].length;
int[][] dp = new int[n][m];
int max = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (i == 0 || j == 0 || matrix[i][j] == ‘0‘) {
dp[i][j] = matrix[i][j] - ‘0‘;
} else {
dp[i][j] = Math.min(dp[i - 1][j - 1],
Math.min(dp[i - 1][j], dp[i][j - 1])) + 1;
}
max = Math.max(max, dp[i][j]);
}
}
return max * max;
}
}
原文：http://www.cnblogs.com/harrygogo/p/4647645.html