概览
一个典型的2D平面上的动态规划问题。给定一个仅有0和1矩阵，找出其中最大的，仅包含1的正方形。
动态规划
状态定义：
定义DP[i][j]表示矩阵M中以位置(i, j)为右下角的最大的正方形的边长。
状态转移方程：
由上述状态定义可知，当M[i][j] == 0时，DP[i][j] = 0；否则DP[i][j]由DP[i - 1][j]、DP[i][j - 1]、DP[i - 1][j - 1]中的最小值决定——考虑这三个值相等时，DP[i][j]可以组合使边长增加1，同时若这三个值不同时增加，都无法再增加DP[i][j]的值。
因此，状态转移方程表示为：
1 | DP[i][j] == 0 if M[i][j] == 0 |
算法的时间复杂度为$O(MN)$，空间复杂度为$O(MN)$，其中输入矩阵为$M \times N$的矩阵。