正文索引 [隐藏]

传送门

思路

记录这道题主要是为了记录二位前缀和的做题思路，毕竟CSP都遇见现题了，当时还只过了8个点…

其实前缀和也是一种形式的dp，这里借用LeetCode-304官方题解的图片，它画得很清晰了

我们设dp[i][j]表示从矩阵左上角(0,0)到当前位置(i,j)的所有值之和，则不难得出图中的转移方程。减去dp[i-1][j-1]的原因是它在计算dp[i][j-1]+dp[i-1][j]中被计算了两次，要减掉多余的那一次。

这种思路在LeetCode周赛#225的T3中也有体现。

当我们对所有的(i,j)都算出前缀和后，用四重循环去依次枚举每一对左上角与右下角就行了。虽然纸面复杂度有O(n²* m²)，但每一个右下角一定在左下角后面，所以对右下角的枚举并没有严格的平方级复杂度，所以还是能把题混过去的。

代码

int sum[110][110];
class Solution {
public:
    int maxSumSubmatrix(vector<vector<int>>& mat, int k) {
        int m = mat.size(), n = mat[0].size();
        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n; j++){
                sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + mat[i - 1][j - 1];
            }
        }
        int ans = INT_MIN;
        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n; j++){
                for(int p = i; p <= m; p++){
                    for(int q = j; q <= n; q++){
                        int cur = sum[p][q] - sum[i - 1][q] - sum[p][j - 1] + sum[i - 1][j - 1];
                        if(cur <= k){
                            ans = max(ans,cur);
                        }
                    }
                }
            }
        }
        return ans;
    }
};