矩阵的最小路径和（动态规划）

题意

给定一个二维0/1数组,求由1构成的最大的正方形是多少

思路分析

题意转换

把问题转换,变成给你同样的数组,你可以从任何0值出发,向右,向下,或向右下走,记录每个格子所需要的最少步数

求最少步数的最大值

证明等价

转换后的题意,意味着每个1的格子的值,表示的是它左上方最近的0格子和它的距离

也就是以这个格子为右下角所产生的正方形的最大边长, 边长的平方就是要求的面积, 和题意等价

递推公式

那么有递推公式

if(matrix[i][j] == 0) continue/return; // 不处理为0的情况
if(matrix[i-1][j] == 0 || matrix[i-1][j-1] == 0 || matrix[i][j-1] == 0){ // 有相邻0格
    dp[i][j] = 1;
}else{ // 左,上,左上全是1
    dp[i][j] = 1 + min(dp[i-1][j] , dp[i-1][j-1], dp[i][j-1]);
}

边界处理

注意到如果让matrix为零值的时候dp直接是0,也适用上面min的表达式.

所以简化为

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

所以最后只需要处理i==0和j==0的边界,以及整个矩阵为0x0的情况

样例数据举例

以题目中的样例数据1为例,产生的辅助数组为

alt

那么2就是最大边长,因此最大面积为4

题解

所以整合上面的内容

class Solution {
public:
    /**
     * 最大正方形
     * @param matrix char字符型vector<vector<>> 
     * @return int整型
     */
    int solve(vector<vector<char> >& matrix) {
        if(matrix.size() == 0)return 0;
        const int INF = 0x3f3f3f3f;
        vector<vector<int> > cnt(matrix.size(),vector<int>(matrix[0].size(),0));
        int ans = 0;
         for(int i = 0;i<matrix.size();i++){
            for(int j = 0;j<matrix[0].size();j++){
                if(matrix[i][j] != '1')continue;
                if(i + j == 0) { // 上边界 左边界
                    cnt[i][j] = 1;
                }else{
                    cnt[i][j] = min(
                        cnt[i-1][j-1], // 左上角
                        min(
                            cnt[i][j-1], // 左侧
                            cnt[i-1][j] // 上方
                        )
                    ) + 1;
                }
                ans = max(ans,cnt[i][j]);
            }
        }
        return ans*ans; // 面积
    }
};

复杂度分析

空间复杂度: 存储状态数组大小和原数组一致,所以空间复杂度为 $O (n^{2})$

时间复杂度: 状态转移代价是常数代价,所以时间复杂度为 $O (n^{2})$

题解 | #最大正方形#