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

糖逗

题目描述：

1. v给你一个由若干 0 和 1 组成的二维网格 grid，请你找出边界全部由 1 组成的最大 正方形 子网格，并返回该子网格中的元素数量。如果不存在，则返回 0。
   
2. 
   
3.  
   
4. 
   
5. 示例 1：
   
6. 
   
7. 输入：grid = [[1,1,1],[1,0,1],[1,1,1]]
   
8. 输出：9
   
9. 示例 2：
   
10. 
    
11. 输入：grid = [[1,1,0,0]]
    
12. 输出：1
    
13.  
    
14. 
    
15. 提示：
    
16. 
    
17. 1 <= grid.length <= 100
    
18. 1 <= grid[0].length <= 100
    
19. grid[i][j] 为&#160;0&#160;或&#160;1
    
20. 
    
21. 来源：力扣（LeetCode）
    
22. 链接：https://leetcode-cn.com/problems/largest-1-bordered-square
    
23. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

1. class Solution {
   
2. public:
   
3.     int largest1BorderedSquare(vector<vector<int>>& grid) {
   
4.         int len1 = grid.size(), len2 = grid[0].size();
   
5.         vector<vector<vector<int> > > dp(len1 + 1, vector<vector<int> >(len2 + 1, vector<int>(2, 0)));
   
6.         int res = 0;
   
7.         for(int i = 1; i <= len1; i++){
   
8.             for(int j = 1; j <= len2; j++){
   
9.                 if(grid[i - 1][j - 1] == 0)continue;
   
10.                 dp[i][j][1] = dp[i][j-1][1] + 1;
    
11.                 dp[i][j][0] = dp[i-1][j][0] + 1;
    
12.                 int len = min(dp[i][j][1], dp[i][j][0]);
    
13.                 while(len > 0){
    
14.                     if(dp[i - len + 1][j][1] >= len && dp[i][j-len + 1][0] >= len)break;
    
15.                     len--;
    
16.                 }
    
17.                 res = max(res, len);
    
18.             }
    
19.         }
    
20.         return res * res;
    
21.     }
    
22. };

复制代码

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