[ 热题 HOT 100]---221. 最大正方形---动态规划

1 题目描述

2 解题思路

动态规划的想法来自于力扣题解，链接为 理解 三者取最小+1

解决方法：动态规划

此时已可得到递推公式

// 伪代码 if (grid[i - 1][j - 1] == '1') { dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1; } 作者：lzhlyle 链接：https://leetcode-cn.com/problems/maximal-square/solution/li-jie-san-zhe-qu-zui-xiao-1-by-lzhlyle/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

复杂度分析： 时间复杂度 O(height * width)O(height∗width) 空间复杂度 O(height * width)O(height∗width)

3 解决代码

解决方法：动态规划《Java代码》 class Solution { public int maximalSquare(char[][] matrix) { if(matrix == null || matrix.length < 1 || matrix[0].length < 1){ return 0; } int m = matrix.length; int n = matrix[0].length; int max = 0; //多建一行一列的0 int[][] dp = new int[m + 1][n + 1]; for(int i = 0; i < m; i++){ for(int j = 0; j < n; j++){ if(matrix[i][j] == '1'){ //取三者的最小值+1，可以类比想一下木桶短板效应 dp[i + 1][j + 1] = Math.min(dp[i][j], Math.min(dp[i + 1][j], dp[i][j + 1])) + 1; max = Math.max(max, dp[i + 1][j + 1]); } } } //求出来的是最长的边长，面积的话要进行相乘 return max * max; } }