最大正方形问题

0. 问题描述

  有M*N个正方形格子,其中一些格子涂成了蓝色,如图1所示。求蓝色格子所能构成的最大正方形边长。图1中蓝色格子所能构成的最大正方形边长为3。

图1

图1

1. 预处理

  使用g[i][j]表示以第i行第j列的格子为右下角,所能构成的最大正方形的边长。对g[i][j]进行初始化:

  • 如果格子为白色,令g[i][j] = 0;
  • 如果格子为蓝色,令g[i][j] = 1。

  得到结果如图2。注意第0行和第0列(g[i][0]和g[j][0])初始化为0。

图2

图2

 

2. 动态规划

  遍历并更新蓝色格子的g[i][j],令g[i][j]等于其上边(g[i – 1][j])、左边(g[i][j – 1])、左上(g[i – 1][j – 1])三个相邻格子的最小值,然后再加1。此时g[i][j]的值表示以第i行第j列的格子为右下角,所能构成的最大正方形的边长。

  g[i – 1][j]、g[i][j – 1]和g[i – 1][j – 1]分别表示了与g[i][j]相邻的三个格子所能构成的最大正方形边长,其中的最小值限制了g[i][j]所能构成的最大正方形边长。由于g[i][j]的加入,在最小值的基础上加1,得到g[i][j]所能构成的最大正方形的边长。

  在上一步中,使用g[i][j]存储第i行第j列的格子的状态,把第0行和第0列空出来不用,初始化为0。遍历所有格子的循环从1开始,这样在访问g[i – 1][j]等格子时,不需要担心越界。即:

  得到结果如图3。

图3

图3

  举例来说,图3中g[3][2]是2,表示了以第3行第2列格子为右下角,能够构成最大正方形的边长为2,即由位于g[3][2],g[3][1],g[2][2],g[2][1]四个格子构成的正方形。

3. 找最大值

  找到g[i][j]中的最大值,即为蓝色格子所能构成的最大正方形边长。图3中g[i][j]最大值为3。

4. 时间复杂度

  上面的算法,第1步初始化和第2步动态规划各需要把所有M*N个格子遍历一遍,时间复杂度为O(MN)。

5. 关于动态规划

  第2步使用了动态规划。动态规划将一个完整的问题不断分解成为若干子问题,使问题能够通过递推的方式解决,通过求解子问题,得到完整问题的解。动态规划的核心是对状态和状态转移方程的定义。

  上面的问题中,g[i][j]是状态,它的定义是“表示以第i行第j列的格子为右下角,所能构成的最大正方形的边长”。通过观察当前状态g[i][j]和之前状态间的关系,得到状态转移方程“g[i][j] = min(g[i – 1][j], g[i][j – 1], g[i – 1][j – 1]) + 1”,这个方程给出了由之前状态(g[i – 1][j]、g[i][j – 1]、g[i – 1][j – 1])计算当前状态(g[i][j])的方法,得到了递推关系,可以通过循环求解。

  对状态和状态转移方程的定义是动态规划的难点,关键在于对问题的充分理解和对问题背后规律的挖掘。