> For the complete documentation index, see [llms.txt](https://timmybeeflin.gitbook.io/cracking-leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://timmybeeflin.gitbook.io/cracking-leetcode/dynamic-programming/specail-square-dp/221.-maximal-square.md).

# 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] 這個正方形加上一行和一列

![](/files/-M2I7anodMnLUEjdhKQF)

![](/files/1gGgSn02clIKjMOHYu8A)

1.子問題

2\. dp function: 

我們能求的其實是邊長

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;
    }
}
```