题目：
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.
链接： http://leetcode.com/problems/maximal-square/
题解：
二维DP，先初始化首行和首列，然后假设matrix[i][j] == ‘1‘，我们可以先设定dp[i][j] = 1，然后根据左上，上，左三个元素中最小的一个来求新的值。代码写得较繁琐，还可以优化空间复杂度。
Time Complexity - O(n2)， Space Complexity - O(n2)
public class Solution { public int maximalSquare(char[][] matrix) { if(matrix == null || matrix.length == 0) return 0; int[][] dp = new int[matrix.length][matrix[0].length]; int max = 0; for(int i = 0; i < matrix.length; i++) { if(matrix[i][0] == ‘1‘) { dp[i][0] = 1; if(max == 0) max = 1; } } for(int j = 0; j < matrix[0].length; j++) { if(matrix[0][j] == ‘1‘) { dp[0][j] = 1; if(max == 0) max = 1; } } for(int i = 1; i < dp.length; i++) { for(int j = 1; j < dp[0].length; j++) { if(matrix[i][j] == ‘1‘) { dp[i][j] = 1; if(dp[i - 1][j - 1] > 0 && dp[i - 1][j] > 0 && dp[i][j - 1] > 0) { int prev = Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1])); prev = (int)Math.sqrt(prev) + 1; prev *= prev; dp[i][j] = prev; max = Math.max(max, prev); } } } } return max; } }
Reference:
原文：http://www.cnblogs.com/yrbbest/p/4990427.html