Simple Python DP solution
Please see and vote for my solution for these similar problems.\n560. Subarray Sum Equals K\n974. Subarray Sums Divisible by K\n325. Maximum Size Subarray Sum E
Please see and vote for my solution for these similar problems.\n[560. Subarray Sum Equals K](https://leetcode.com/problems/subarray-sum-equals-k/discuss/344431/Simple-Python-DP-solution)\n[974. Subarray Sums Divisible by K](https://leetcode.com/problems/subarray-sums-divisible-by-k/discuss/344436/Simple-Python-DP-solution)\n[325. Maximum Size Subarray Sum Equals k](https://leetcode.com/problems/maximum-size-subarray-sum-equals-k/discuss/344432/Simple-Python-DP-solution)\n[1074. Number of Submatrices That Sum to Target](https://leetcode.com/problems/number-of-submatrices-that-sum-to-target/discuss/344440/Simple-Python-DP-solution)\n[363. Max Sum of Rectangle No Larger Than K](https://leetcode.com/problems/max-sum-of-rectangle-no-larger-than-k/discuss/445540/Python-bisect-solution-(960ms-beat-71.25))\n\nFor each row, calculate the prefix sum. For each pair of columns, calculate the sum of rows. \nNow this problem is changed to problem 560 Subarray Sum Equals K.\n```\n    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:\n        m, n = len(matrix), len(matrix[0])\n        for x in range(m):\n            for y in range(n - 1):\n                matrix[x][y+1] += matrix[x][y]\n        res = 0\n        for y1 in range(n):\n            for y2 in range(y1, n):\n                preSums = {0: 1}\n                s = 0\n                for x in range(m):\n                    s += matrix[x][y2] - (matrix[x][y1-1] if y1 > 0 else 0)\n                    res += preSums.get(s - target, 0)\n                    preSums[s] = preSums.get(s, 0) + 1\n        return res\n```
[]