221. 最大正方形（动态规划）

本文主要是介绍221. 最大正方形（动态规划），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

将最大正方形面积问题转化成最大边长问题。

动态规划：

• 状态定义：
  • dp[i][j]表示以第i行第j列元素为最右下角的最大正方形边长。
  • 在状态转移的过程中，取到dp[i][j]的最大值即为最大边长，其平方即为答案。
• 状态转移：
  • 如果matrix[i][j]=0，则不能构成正方形，dp[i][j]=0；
  • 如果matrix[i][j]=1，则检查其左边、左上角及上边元素的dp值，取最小值+1。
• 状态初始化：
  • 首行首列元素如果值为0，dp=0，如果值为1，dp=1

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

这篇关于221. 最大正方形（动态规划）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---