最大正方形动态规划解法

一、须知

题解简略，仅供参考。

答主水平有限，如有错误请在评论区提醒一下，有更好的解法或改进代码也欢迎来一起探讨。十分感谢！

二、题解

根据DP解题的三步骤

1.确定dp[][]数组的含义

此题的dp[i][j]，代表以坐标为(i,j)的元素为右下角的正方形的边长。

2.状态转移方程

dp[i][j]的值取决于dp[i-1][j],dp[i-1][j-1],dp[i][j-1]的最小值
即左方正方形的边长，左上方正方形的边长，上方正方形的边长三者的最小值。

3.边界

由于状态转移方程中涉及i-1，j-1，所以i和j一定要大于0.
故dp[0][] 和 dp[][0]要首先确定。

故得到以下代码。

import java.util.*;

public class Solution {
    /**
     * 最大正方形
     * @param matrix char字符型二维数组 
     * @return int整型
     */
    public int solve (char[][] matrix) {
        // write code here
        if(matrix.length ==0 || matrix[0].length == 0) return 0;
        int rows = matrix.length;
        int cols = matrix[0].length;
        int[][] dp = new int[rows][cols];
        int maxSquareLength = 0;
        for(int i = 0; i < rows; i++){
            if(matrix[i][0] == '1') dp[i][0] = 1;
        }
        for(int i = 0; i < cols; i++){
            if(matrix[0][i] == '1') dp[0][i] = 1;
         }
        for(int  i =1; i < rows; i++){
            for(int j = 1; j < cols; j++){
                if(matrix[i][j] == '1'){
                    dp[i][j] = Math.min(Math.min(dp[i-1][j-1],dp[i-1][j]),dp[i][j-1])+1;
                    if(dp[i][j] > maxSquareLength) maxSquareLength = dp[i][j];
                }
            }
        }
        return maxSquareLength*maxSquareLength;
    }
}