C++刷LeetCode（85. 最大矩形）【动态规划】

糖逗

题目描述：

给定一个仅包含 0 和 1 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。

示例:

输入:
[
  ["1","0","1","0","0"],
  ["1","0","1","1","1"],
  ["1","1","1","1","1"],
  ["1","0","0","1","0"]
]
输出: 6

class Solution {
public:
    struct compair{
        int up;
        int left;
    };
    int maximalRectangle(vector<vector<char>>& matrix) {
        if(matrix.empty()) return 0;
        int len1 = matrix.size(), len2 = matrix[0].size();
        vector<vector<compair> >dp(len1 + 1, vector<compair>(len2 + 1, {0, 0}));
        int res = 0;
        for(int i = 1; i <= len1; i++){
            for(int j = 1; j <= len2; j++){
                if(matrix[i - 1][j - 1] != '1') continue;
                dp[i][j].up = dp[i-1][j].up + 1;
                dp[i][j].left = dp[i][j-1].left + 1;
                int store1 = dp[i][j].left;
                int number1 = 1;
                for(int m = i; m >= i - dp[i][j].up + 1; m--){
                    store1 = min(store1, dp[m][j].left);
                    res = max(res, store1 * number1);
                    number1++;
                }
                int store2 = dp[i][j].up;
                int number2 = 1;
                for(int n = j; n >= j - dp[i][j].left + 1; n--){
                    store2 = min(store2, dp[i][n].up);
                    res = max(res, store2 *number2);
                    number2++;
                }
            }
        }
        return res;
    }
};

糖逗

类比：https://fishc.com.cn/forum.php?m ... =%D5%FD%B7%BD%D0%CE
https://fishc.com.cn/forum.php?m ... =%D5%FD%B7%BD%D0%CE

糖逗