问题描述

  1. 在一个由0，1组成的矩阵中找到只包含1的最大正方形，并返回其面积。
  2. https://leetcode-cn.com/problems/maximal-square/

收获

  1. 首先你得能把暴力法描述出来
    • 首先遍历矩阵找到所有元素等于1的位置。
    • 以该元素为左上角，寻找可能的最大正方形的边长
    • 每次在下面新增一行并在右面新增一列，判断是否满足正方形内的元素都是1
  2. 关键在于状态转移方程：dp(i,j)表示以（i，j）为右下角，且只包含1的正方形的边长最大值，则$dp(i,j)=min(dp(i-1,j),dp(i,j-1),dp(i-1,(j-1))$. 正方形相对于矩形还是简单了很多的。
  3. 这道题目类似于LeeCode1277 统计全为1的正方形子矩阵。