LeetCode 221 最大正方形

本题是一道常见的动态规划题目，关键点在于子问题状态的定义。

题目描述

原题链接如下： LeetCode 221 最大正方形

题目大意

本题中矩阵只包含 0 或者 1，而且对最大正方形的位置没有特殊的规定。

输入与输出

示例输入：

1
2
3
4

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

示例输出：

1

4

注意：本题输入的矩阵内容为字符，而不是整数。

解题思路

矩阵内的正方形子矩阵很好定义，只要它的任意一个角确定了位置，并且边长确定，那么正方形就必然确定。而我们处理问题时，一般时按照逐行再逐列的方法进行扫描，那么不妨固定正方形的右下角方便逐步扩大正方形边长，以检查正方形是否只包含 1。 假设我们要检查单元格 (i, j) 为右下角的正方形，那么它可以被拆分为 4 个部分：

• (i - 1, j - 1) 为右下角的正方形
• (i - 1, j) 及其上方的一列
• (i, j - 1) 及其左侧的一行
• (i, j) 单元格本身

如果，我们严格逐行又逐列扫描，那么上面的前 3 个部分实际早就知道了它们包含 1 的最大的大小，即动态规划中的子问题状态可递推确定。而且，我们又注意到虽然第 2 和第 3 部分只要求获取一列或一行的连续 1 的个数，但是实际上只要第 1 部分能构造出正方形，那么这两条边就也能借助第 1 部分的单元格构造出正方形，而且边长一定不大于第 1 部分的正方形。 这样，可以构造 dp(i, j) 为以 (i, j) 为右下角的只包含 1 的正方形的最大边长，其递推式如下：

$$ dp(i,j)=\begin{cases} 0 & matrix[i, j] = 0 \\ min{\lbrace dp(i - 1, j - 1),\ dp(i - 1, j),\ dp(i, j - 1) \rbrace} + 1 & matrix[i, j] = 1 \end{cases} $$

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    fun maximalSquare(matrix: Array<CharArray>): Int {
        if (matrix.isEmpty()) return 0

        var re = 0
        val m = matrix.size
        val n = matrix[0].size
        val dp = Array(m + 1) { IntArray(n + 1) }
        for (i in 1..m) {
            for (j in 1..n) {
                if (matrix[i - 1][j - 1] == '0') continue

                dp[i][j] = minOf(dp[i - 1][j - 1], minOf(dp[i - 1][j], dp[i][j - 1])) + 1
                re = maxOf(re, dp[i][j])
            }
        }
        return re * re
    }
}