[C++] DP brute force and 2-sum flavored, a legend a 1-D guy manage 2-D dream
Approach 1: DP [1]\nTime/Space: O(M*N^2); O(1); where M, N is the row and column size of the given matrix\nmotivation:\nIt is about a legend a 1-D guy manage 2-
Approach 1: DP [1]\nTime/Space: O(M*N^2); O(1); where M, N is the row and column size of the given matrix\nmotivation:\nIt is about a legend a 1-D guy manage 2-D dream\n```\nclass Solution {\npublic:\n    int numSubmatrixSumTarget(vector<vector<int>>& matrix, int target) {\n        const int m = matrix.size(), n = matrix[0].size();\n        for(int i = 0; i < m; i++)\n            for(int j = 1; j < n; j++)\n                matrix[i][j] += matrix[i][j-1];\n        \n        int ans = 0;\n        for(int l = 0; l < n; l++) // l: left column index\n            for(int r = l; r < n; r++){ //r: right column index\n                unordered_map<int, int> counts{{0, 1}};\n                int cur = 0; //this guy working hard, coming from 1-D world, but can watch 2-D by collecting runnign rums of different rows between col l & r\n                for(int i = 0; i < m; i++){\n                    cur += matrix[i][r] - (l > 0 ? matrix[i][l - 1] : 0);                    \n                    ans += counts[cur - target];\n                    ++counts[cur];\n                }                \n            }\n        return ans;        \n    }\n};\n```\n\n\nApproach 2: DP brute force (WARNING: will cause TLE error)\nTime/Space: O(N^4); O(N)\n```\nclass Solution {\npublic:\n    int numSubmatrixSumTarget(vector<vector<int>>& matrix, int target) {\n        const int m = matrix.size(), n = matrix[0].size();\n        vector<vector<int>> sums(m + 1, vector<int>(n + 1, 0));\n        for(int i = 1; i <= m; i++)\n            for(int j = 1; j <= n; j++)\n                sums[i][j] = sums[i - 1][j] + sums[i][j - 1] - sums[i - 1][j - 1] + matrix[i-1][j-1];\n        \n        int ans = 0;\n        for(int i = 1; i <= m; i++)\n            for(int j = 1; j <= n; j++)\n                for(int r = 1; r <= i; r++)\n                    for(int c = 1; c <= j; c++)\n                        if(target == sums[i][j] - sums[i][c - 1] - sums[r - 1][j] + sums[r - 1][c - 1]) ans++;\n        return ans;\n    }\n};\n```\n\n[1] https://www.cnblogs.com/grandyang/p/14588186.html
[]