力扣(LeetCode)221

题目地址：

https://leetcode-cn.com/probl...

题目描述：

在一个由 0 和 1 组成的二维矩阵内，找到只包含 1 的最大正方形，并返回其面积。

示例:

输入:

1 0 1 0 0

1 0 1 1 1

1 1 1 1 1

1 0 0 1 0

输出: 4

解答：

这一题使用动态规划算法。dpi表示以点(i,j)为右下角点的最大正方形的边长，那么就有若matrixi = '0'，dpi = 0,否则dpi = 1+min(dpi-1,min(dpi-1,dpi))

然后查找dpi的最大值max，返回max*max

java ac代码:

class Solution {
    public int maximalSquare(char[][] matrix) {
        if(matrix.length == 0)return 0;
        
        int[][]dp = new int[matrix.length][matrix[0].length];
        for(int i = 0;i < matrix.length;i++)
            dp[i][0] = matrix[i][0]-'0';
        for(int j = 0;j < matrix[0].length;j++)
            dp[0][j] = matrix[0][j]-'0';
        
        for(int i = 1;i < matrix.length;i++)
            for(int j = 1;j < matrix[0].length;j++)
                if(matrix[i][j] != '0')
                dp[i][j] = 1+Math.min(Math.min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1]);
        
        int max = 0;
        for(int i = 0;i < matrix.length;i++)
            for(int j = 0;j < matrix[0].length;j++)
                max = Math.max(dp[i][j],max);
        return max*max;
    }
}