经典算法题之Maximal Square

作者：叶 虎

编辑：邓高锦

Maximal Square是道非常有意思的算法题。它是一个典型的动态规划问题，同时也是2017京东面试题，2016华为机考题。

1

题目描述：

有一个n*m大小的矩阵，其元素值为0或者1，求这个矩阵中全有1组成的最大方块其大小。

2

输入描述

每个输入包含一个测试用例。每个测试用例的第一行包含两个整数n（2<= n <= 50），m（2<= n <= 50），分别表示矩阵matrix的行数与列数。接下来的每一行是该矩阵的每一行元素，其取值为1或者0。

3

输出描述

输出矩阵中全有1组成的最大方块其大小。

4

输入例子

4 6

1 1 0 1 1 1

0 1 1 1 1 1

1 1 0 1 1 1

1 1 0 0 1 1

5

输出例子

3

思路分析：

本题为一个典型的动态规划问题，因此可以使用动态规划的思想进行。动态规划重要的一个特点是要复用子问题。

假设以matrix[i][j]为右下顶点的最大方块的大小为dp[i][j]。那么dp[i][j]的计算否可以复用比其更小的子问题呢？不难想象，如果matrix[i][j]=0，那么dp[i][j]=0。当matrix[i][j]=1时，此时要考察dp[i-1][j-1]，dp[i-1][j]及dp[i][j-1]，这是由于以matrix[i][j]的为右下顶点的最大方块由上面三个位置决定，而且是木桶效应，由最小值所决定，即dp[i][j]=min{dp[i-1][j-1], dp[i-1][j], dp[i][j-1]} + 1。考虑到边界条件，可以得到最终的递归方程为：

只需要找到最大的dp[i][j]值即得到最大方块的大小。整个算法的时间复杂度与空间复杂度均为O(n*m)。

具体实现代码(C++)

本文只是Maximal Square算法题其中的一种解法，在此抛砖引玉。