最大正方形
在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积。
示例 1：
codeType
输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
输出：4
示例 2：
codeType
输入：matrix = [["0","1"],["1","0"]]
输出：1
示例 3：
codeType
输入：matrix = [["0"]]
输出：0
提示：
- m == matrix.length
- n == matrix[i].length
- 1 <= m, n <= 300
- matrix[i][j] 为 '0' 或 '1'
解法
ts
function maximalSquare(matrix: string[][]): number {
// dp[i][j] 表示i，j为右下角的正方形的边长最大值
// 如果matrix[i][j] === '1'，那么dp[i][j]的边长就是相邻的三个元素的值 + 1
// 所以有 dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - 1], dp[i][j - 1]) + 1
const n = matrix.length
const m = matrix[0].length
const dp = new Array(n + 1).fill(0).map(() => new Array(m + 1).fill(0))
let maxSize = 0
for(let i = 0; i <= n; i++){
for(let j = 0; j <= m; j++){
if(i > 0 && j > 0 && matrix[i - 1][j - 1] === '1'){
dp[i][j] = Math.min(dp[i - 1][j], dp[i - 1][j - 1], dp[i][j - 1]) + 1
}else if(i === 0 || j === 0){
dp[i][j] = 0
}
maxSize = Math.max(maxSize, dp[i][j])
}
}
return maxSize * maxSize
};