[Python] cumulative sum + dp, explained
Let us define by dp[i, j, k] sum of numbers in the rectangle i <= x < j and 0 <= y < m. Why it is enough to evaluate only values on these matrices? Because then
Let us define by `dp[i, j, k]` sum of numbers in the rectangle `i <= x < j` and `0 <= y < m`. Why it is enough to evaluate only values on these matrices? Because then we can use **2Sum** problem: any sum of elements in submatrix with coordinates `a <= x < b` and `c <= y < d` can be evaluated as difference between sum of `a <= x < b, 0 <= y < d` and sum of `a <= x < b, 0 <= y < c`. So, let us fix `a` and `b`, and say we have sums `S1, S2, ... Sm`.  Then we want to find how many differences between these values give us our `target`. The idea is to calculate cumulative sums and keep counter of values, and then check how many we have (we can not use sliding window, because we can have negative values), see problem **560**. Subarray Sum Equals K for more details.\n\nSo, we have in total two stages of our algorithm:\n1. Precompute all sums in rectangles of the type `i <= x < j` and `0 <= y < m`.\n2. For each `n*(n-1)/2` problems with fixed `i` and `j`, solve sumproblem in `O(m)` time.\n\n#### Complexity\nTime complexity is `O(n^2m)`, we need it for both stages. Space complexity is the same.\n\n#### Code\n\n```\nclass Solution:\n    def numSubmatrixSumTarget(self, matrix, target):\n        m, n = len(matrix), len(matrix[0])\n        dp, ans = {}, 0\n        for k in range(m):\n            t = [0] + list(accumulate(matrix[k]))\n            for i, j in combinations(range(n+1), 2):\n                dp[i, j, k] = dp.get((i,j,k-1), 0) + t[j] - t[i]\n        \n        for i, j in combinations(range(n+1), 2):\n            T = Counter([0])\n            for k in range(m):\n                ans += T[dp[i, j, k] - target]\n                T[dp[i, j, k]] += 1\n                \n        return ans\n```\n\nIf you have any questions, feel free to ask. If you like solution and explanations, please **Upvote!**
['Dynamic Programming']