C++刷LeetCode（1139. 最大的以 1 为边界的正方形）【动态规划】

糖逗

题目描述：

v给你一个由若干 0 和 1 组成的二维网格 grid，请你找出边界全部由 1 组成的最大 正方形 子网格，并返回该子网格中的元素数量。如果不存在，则返回 0。

 

示例 1：

输入：grid = [[1,1,1],[1,0,1],[1,1,1]]
输出：9
示例 2：

输入：grid = [[1,1,0,0]]
输出：1
 

提示：

1 <= grid.length <= 100
1 <= grid[0].length <= 100
grid[i][j] 为 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[0].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[i - 1][j - 1] == 0)continue;
                dp[i][j][1] = dp[i][j-1][1] + 1;
                dp[i][j][0] = dp[i-1][j][0] + 1; 
                int len = min(dp[i][j][1], dp[i][j][0]);
                while(len > 0){
                    if(dp[i - len + 1][j][1] >= len && dp[i][j-len + 1][0] >= len)break;
                    len--;
                }
                res = max(res, len);
            }
        }
        return res * res;
    }
};

参考链接：https://leetcode-cn.com/problems ... ui-hua-by-koishi-7/
注意事项：注意dp的定义，这里考虑了后面i-1和j-1越界的问题同时i=0和j=0都需要加入循环中。这里没有dp的提前填充。