C++刷LeetCode（1139. 最大的以 1 为边界的正方形）【动态规划】
题目描述：v给你一个由若干 0 和 1 组成的二维网格 grid，请你找出边界全部由 1 组成的最大 正方形 子网格，并返回该子网格中的元素数量。如果不存在，则返回 0。
示例 1：
输入：grid = [,,]
输出：9
示例 2：
输入：grid = []
输出：1
提示：
1 <= grid.length <= 100
1 <= grid.length <= 100
grid 为 0 或 1
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/largest-1-bordered-square
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
class Solution {
public:
int largest1BorderedSquare(vector<vector<int>>& grid) {
int len1 = grid.size(), len2 = grid.size();
vector<vector<vector<int> > > dp(len1 + 1, vector<vector<int> >(len2 + 1, vector<int>(2, 0)));
int res = 0;
for(int i = 1; i <= len1; i++){
for(int j = 1; j <= len2; j++){
if(grid == 0)continue;
dp = dp + 1;
dp = dp + 1;
int len = min(dp, dp);
while(len > 0){
if(dp >= len && dp >= len)break;
len--;
}
res = max(res, len);
}
}
return res * res;
}
};
参考链接：https://leetcode-cn.com/problems/largest-1-bordered-square/solution/c-dong-tai-gui-hua-by-koishi-7/
注意事项：注意dp的定义，这里考虑了后面i-1和j-1越界的问题同时i=0和j=0都需要加入循环中。这里没有dp的提前填充。
页:
[1]