LeetCode 221.Maximal Square with DP

题目描述

Given a 2D binary matrix filled with 0’s and 1’s, find the largest square containing only 1’s and return its area.

For example, given the following matrix:
1
2
3
4
5
>1 0 1 0 0
>1 0 1 1 1
>1 1 1 1 1
>1 0 0 1 0
>

Return 4.

原题链接

算法分析

考虑使用动态规划解决。首先需要找到状态转移方程。

最直接会想到使用dp[i][j]来表示“在matrix[0][0]到matrix[i][j]中所能找到的最大的正方形面积”。但是显然，dp[i][j]这一状态是很难用之前的某些状态来表示的。

不妨尝试使用dp[i][j]来表示“以matrix[i][j]作为正方形右下角的方形面积”，这样只需找到所有dp[i][j]中的最大值即可。这样仍然有一定难度表示，因此可以转化为用dp[i][j]表示“以matrix[i][j]作为正方形右下角的正方形边长”。想找到状态转移方程，首先考虑dp[i][j]和之前的哪些状态有关，显然是dp[i-1][j]，dp[i][j-1]和dp[i-1][j-1]。不难知道，当matrix[i][j]为‘0’是，dp[i][j]必然是为0的，下面考虑matrix[i][j]是’1’时的情况：

首先，最理想的是下面这种情况：

1
2
3

1 1 1
1 1 1
1 1 X

此时，matrix[1][2]，matrix[2][1]和matrix[1][1]都分别是某一个方形的右下角，且边长分别是2，2，2，加上matrix[2]后，恰好能将当前已有的方形边长增加1。即dp[2][2]为3。

但如果这三个方形边长不相等呢：

1
2
3

1 1 0
1 1 1
1 1 X

如上例，此时dp[i-1][j]，dp[i][j-1]，dp[i-1][j-1]分别是1，2，2。而dp[i][j]显然为2。这是因为，由于dp[i-1][j]为1，限制了dp[i][j]的值只能在此基础上增加为2，因为在竖直方向上无法组成更大的方形。根据这些规律，不难得出实际的状态方程：

1	dp[i][j] = min(dp[i-1][j]，dp[i][j-1]，dp[i-1][j-1]) + 1;

代码实现

有了状态方程，整个算法就不难实现了。为了先得到需要的状态，计算顺序为从上到下，从左到右。代码实现如下：

class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        int m = matrix.size();
        if (m == 0) {
            return 0;
        }
        int n = matrix[0].size();
        vector<vector<int>> dp(m, vector<int>(n, 0));
        int maxlength = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == '0') {
                    dp[i][j] == 0;
                }
                else {
                    int left = j >= 1 ? dp[i][j - 1] : 0;
                    int up = i >= 1 ? dp[i - 1][j] : 0;
                    int upleft = (i >= 1 && j >= 1) ? dp[i - 1][j - 1] : 0;
                    dp[i][j] = min(min(left, up), upleft) + 1;
                    if (dp[i][j] > maxlength) {
                        maxlength = dp[i][j];
                    }
                }
            }
        }
        return maxlength * maxlength;
    }
};

本文为博主原创文章，转载请注明出处。