【LeetCode】221. 最大正方形

动态规划解题

重点要找到状态转移方程：

dp(i,j)=min(dp(i−1,j),dp(i−1,j−1),dp(i,j−1))+1

诀窍是，遍历到某个位置，以它为正方形的右下角。那么正方形的边长是，左邻点，上邻点，左上邻点的最小值加一。

public int maximalSquare(char[][] matrix) {
    // 诀窍是，遍历到某个位置，以它为正方形的右下角
    // 那么正方形的边长是，左邻点，上邻点，左上邻点的最大值加一。
    if (matrix.length == 0) return 0;
    int row = matrix.length;
    int column = matrix[0].length;
    int res = 0;
    int[][] mark = new int[row][column];

    for (int i = 0; i < column; i++) {
        if (matrix[0][i] == '1') {
            mark[0][i] = 1;
            res = 1;
        } else mark[0][i] = 0;
    }
    for (int i = 0; i < row; i++) {
        if (matrix[i][0] == '1') {
            mark[i][0] = 1;
            res = 1;
        } else mark[i][0] = 0;
    }

    for (int i = 1; i < row; i++) { //行遍历
        for (int j = 1; j < column; j++) {// 列遍历
            if (matrix[i][j] == '0') continue;
            int tmp = Math.min(mark[i][j - 1], mark[i - 1][j]);
            int max = Math.min(tmp, mark[i - 1][j - 1]);
            mark[i][j] = max + 1;
            if ((max + 1) > res) res = max + 1;
        }
    }
    return res * res;
}