【算法训练-动态规划 五】【二维DP问题】最大正方形

废话不多说，喊一句号子鼓励自己：程序员永不失业，程序员走向架构！本篇Blog的主题是【动态规划】，使用【数组】这个基本的数据结构来实现，这个高频题的站点是：CodeTop，筛选条件为：目标公司+最近一年+出现频率排序，由高到低的去牛客TOP101去找，只有两个地方都出现过才做这道题（CodeTop本身汇聚了LeetCode的来源），确保刷的题都是高频要面试考的题。

明确目标题后，附上题目链接，后期可以依据解题思路反复快速练习，题目按照题干的基本数据结构分类，且每个分类的第一篇必定是对基础数据结构的介绍。

最大正方形【MID】

来解决一道最大正方形的题目

题干

解题思路

原题解出处按照动态规划的标准解题讨论来进行解题，理解 min(上, 左, 左上) + 1，如题，在其他动态规划方法的题解中，大都会涉及到下列形式的代码：

// 伪代码
if (matrix(i , j ) == '1') {dp(i, j) = min(dp(i - 1, j), dp(i, j - 1), dp(i - 1, j - 1)) + 1;
}

其中，dp(i, j) 是以 matrix(i , j ) 为 右下角 的正方形的最大边长，

若某格子值为 1，则以此为右下角的正方形的、最大边长为：上面的正方形、左面的正方形或左上的正方形中，最小的那个，再加上此格

先来阐述简单共识

• 若形成正方形（非单 1），以当前为右下角的视角看，则需要：当前格、上、左、左上都是 1
• 可以换个角度：当前格、上、左、左上都不能受 0 的限制，才能成为正方形

上面详解了 三者取最小 的含义：

• 图 1：受限于左上的 0
• 图 2：受限于上边的 0
• 图 3：受限于左边的 0

数字表示：以此为正方形右下角的最大边长；黄色表示：格子 ? 作为右下角的正方形区域。就像 木桶的短板理论 那样——附近的最小边长，才与 ? 的最长边长有关。 此时已可得到递推公式

// 伪代码
if (grid[i][j] == '1') {dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1;
}

1 定义状态（定义子问题）

dp 具体定义：dp[i ][j ] 表示 「以第 i 行、第 j 列为右下角的正方形的最大边长」

为何不是 dp[i][j]，回到图解中，任何一个正方形，我们都「依赖」当前格 左、上、左上三个方格的情况，但第一行的上层已经没有格子，第一列左边已经没有格子，需要做特殊 if 判断来处理，为了代码简洁，我们 假设补充 了多一行全 ‘0’、多一列全 ‘0’

2 状态转移方程（描述子问题之间的联系）

取自己左上、上方、左边最小值再加上自身

// 伪代码
if (grid[i][j] == '1') {dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1;
}

3 初始化状态

初始值就是将第一列 dp[row][0] 、第一行 dp[0][col] 都赋为 0，相当于已经计算了所有的第一行、第一列的 dp 值

4 求解方向

这里采用自底向上，从最小的状态开始求解

5 找到最终解

题目要求面积。根据 「面积 = 边长 x 边长」可知，我们只需求出 最大边长 即可,定义 maxSide 表示最长边长，每次得出一个 dp，就 maxSide = max(maxSide, dp); 最终返回 return maxSide * maxSide;

代码实现

给出代码实现基本档案

基本数据结构：数组
辅助数据结构：无
算法：动态规划
技巧：无

其中数据结构、算法和技巧分别来自：

• 10 个数据结构：数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Trie 树
• 10 个算法：递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法
• 技巧：双指针、滑动窗口、中心扩散

当然包括但不限于以上

import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可*** @param nums int整型一维数组* @return int整型一维数组*/public int maximalSquare(char[][] matrix) {// 1 入参校验if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {return 0;}// 2 定义最长边，以及获取边长int maxSide = 0;int row = matrix.length;int col = matrix[0].length;// 3 定义dp数组,dp[i][j]表示以i、j为坐标的元素作为右下角的最大正方形边长，默认初始化了两列0int[][] dp = new int[row + 1][col + 1];// 4 编写状态转移方程for (int i = 1; i <= row; i++) {for (int j = 1; j <= col; j++) {if (matrix[i - 1][j - 1] == '1') {dp[i][j] = Math.min(dp[i - 1][j], Math.min(dp[i][j - 1], dp[i - 1][j - 1])) + 1;maxSide = Math.max(maxSide, dp[i][j]);}}}return maxSide * maxSide;}
}

考虑到每个方格都需要参与计算，双重循环要从索引1开始（否则dp[0][0]无法进行状态转移，会数组越界），这样为了第0行第0列可以参与计算，就给dp数组补了0，也就是base case，补0后dp的第1行和第1列对应的判断元素其实是matrix的第0行和第0列，所以这里的if条件是：matrix[i - 1][j - 1] == '1'

复杂度分析

时间复杂度：O(N^2)，这里 N 是数组的长度，我们写了两个 for 循环，每个 for 循环的时间复杂度都是线性的；
空间复杂度：O(N)，要使用和输入数组长度相等的状态数组，因此空间复杂度是 O(N)。