# 221. Maximal Square (2D-dp)

如果 matrix\[i-1]\[j-1] == 0 ，DP\[i, j] 也是 0，因為 square 不存在

如果 matrix\[i-1]\[j-1] == 1，那麼 DP\[i, j] 就有以下幾種可能

1）從DP \[i-1,j] 這個形狀 加上一行

2）從DP \[i, j-1] 這個形狀 加上一列

3）從DP \[i-1, j-1] 這個正方形加上一行和一列

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LekNH5IywF8mjBxFcnu%2F-M2DEFuPgE3UgSb11bWm%2F-M2I7anodMnLUEjdhKQF%2Fimage.png?alt=media\&token=bad31f92-2d55-4858-919b-9db77c312599)

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-LekNH5IywF8mjBxFcnu%2Fuploads%2FEYG1JOCd8xVPZ11jJM1u%2F%E5%9C%96%E7%89%87.png?alt=media\&token=36537865-fae1-4421-89e9-c8683b435ef8)

1.子問題

2\. dp function:&#x20;

我們能求的其實是邊長

dp\[i]\[j]: base on right down corner i,j - the larget side length (注意是邊長

dp\[i]\[j] = Math.min(Math.min(dp\[i-1]\[j], dp\[i]\[j-1]), dp\[i-1]\[j-1]) + 1;



注意這題要求的是面積, 所以邊長\*邊長

```java
/*
    time complexity: O(m*n), space complexity: O(m*n), m is matrix's width, n is matrix's height
*/

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



same idea as 1277. Count Square Submatrices with All Ones

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