leetcode 221. 最大正方形

爱被打了一巴掌 2023-06-08 06:43 24阅读 0赞

**dp\[i\]\[j\]表示以（i，j）为右下角的正方形最大的边长**

**转态转移方程：**

matrix[i][j]=='1':
    	dp[i][j] = 1+min( dp[i-1][j-1], min( dp[i][j-1],dp[i-1][j] ));
    matrix[i][j]=='0':
    	dp[i][j] = 0;

**先初始化行和列**

class Solution { 
    public:
        int maximalSquare(vector<vector<char>>& matrix) { 
            int ret = 0;
            if( matrix.size()==0 ){ 
                return 0;
            }
            vector<vector<int> > dp(matrix.size(), vector<int>(matrix[0].size(),0));
            for(int i = 0;i < dp.size();i ++){ 
                if( matrix[i][0] == '1' ){ 
                    dp[i][0] = 1;
                }else{ 
                    dp[i][0] = 0;
                }
                ret = max(ret,dp[i][0]*dp[i][0]);
            }
            for(int i = 0;i < dp[0].size();i ++){ 
                if( matrix[0][i] == '1' ){ 
                    dp[0][i] = 1;
                }else{ 
                    dp[0][i] = 0;
                }
                ret = max(ret,dp[0][i]*dp[0][i]);
            }
            for(int i = 1;i < dp.size();i ++){ 
                for(int j = 1;j < dp[i].size();j ++){ 
                    if(matrix[i][j]== '1'){ 
                        dp[i][j] = 1;
                    }else{ 
                        dp[i][j] = 0;
                        continue;
                    }
                    dp[i][j] += min( dp[i-1][j-1], min( dp[i][j-1],dp[i-1][j] ));
                    ret = max(ret,dp[i][j]*dp[i][j]);
                }
            }
            return ret;
        }
    };

![在这里插入图片描述][20191017133736407.png]

[20191017133736407.png]: /images/20230531/6f06102f51fc4f079eded93e91a6acde.png

发表评论取消回复

表情：

评论列表（有 0 条评论，24人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode-221. 最大正方形

目录题目思路动态规划动态规划(优化) 题目来源 [221. 最大正方形][221.] 题目思路现在我们

一时失言乱红尘/ 2024年03月23日 10:06/ 0 赞/ 165 阅读

相关 221. 最大正方形

打卡!!!每日一题今天继续给大家分享一道动态规划类型的题目，不过该题目的状态转移方程比较难以理解，我会详细的给大家分析一下题目描述： > 在一个由 ‘0’ 和 ‘1’

川长思鸟来/ 2023年10月11日 18:04/ 0 赞/ 69 阅读

相关 leetcode221 最大正方形

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9mYW50aWFuenVvLmJsb2cuY3Nk

拼搏现实的明天。/ 2023年06月17日 04:58/ 0 赞/ 65 阅读

相关 leetcode 221. 最大正方形

dp\[i\]\[j\]表示以（i，j）为右下角的正方形最大的边长转态转移方程： matrix[i][j]=='1': dp[i][j] = 1+min

爱被打了一巴掌/ 2023年06月08日 06:43/ 0 赞/ 25 阅读

相关 221. 最大正方形

在一个由 0 和 1 组成的二维矩阵内，找到只包含 1 的最大正方形，并返回其面积。示例: 输入: 1 0 1 0 0 1 0 1 1 1 1 1 1 1 1

小灰灰/ 2023年05月29日 15:27/ 0 赞/ 56 阅读

相关 LeetCode 221.最大正方形解法

/ LeetCode 221.最大正方形形成22的小正方形，基础上 [ [a, b] [c, d(?)] ]

悠悠/ 2023年03月13日 01:57/ 0 赞/ 87 阅读

相关 221. 最大正方形

题目： [221. 最大正方形][221.] ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_te

爱被打了一巴掌/ 2023年03月04日 14:28/ 0 赞/ 95 阅读

相关 221最大正方形

一、前言标签：动态规划、栈运用、双指针。问题来源LeetCode 5 难度：中等。问题链接：[https://leetcode-cn.com/problems/

深藏阁楼爱情的钟/ 2023年02月28日 15:26/ 0 赞/ 65 阅读

相关 Leetcode 221 最大正方形(DP)

题目重述在一个由 ‘0’ 和 ‘1’ 组成的二维矩阵内，找到只包含 ‘1’ 的最大正方形，并返回其面积。示例 1： ![在这里插入图片描述][watermark

墨蓝/ 2022年08月29日 14:54/ 0 赞/ 208 阅读

相关 LeetCode-221. 最大正方形

[221. 最大正方形][221.] 在一个由 0 和 1 组成的二维矩阵内，找到只包含 1 的最大正方形，并返回其面积。示例: 输入: 1 0 1 0

墨蓝/ 2022年01月27日 01:23/ 0 赞/ 285 阅读