Python | Using Range Sum Query 2D  O(M^2N) | M<N | Faster | 99%
Similar to LC 304: Range Sum Query 2D| Approach 4, create a 2D cache : dp such that  dp(row,col) is the sum of the subarray (0,0) to (row,col)\n\nNow, applying 
Similar to [LC 304: Range Sum Query 2D| Approach 4](https://leetcode.com/problems/range-sum-query-2d-immutable/), create a 2D cache : dp such that  dp(row,col) is the sum of the subarray (0,0) to (row,col)\n\nNow, applying logic similar to [LC 560: Subarray sum equals k](https://leetcode.com/problems/subarray-sum-equals-k/) we need to create a hashmap but since this is in 2D, we fix the row limits row1 and row2. Then iterate through the columns calculating the presum of the subarray up till that column for the fixed (row1, row2), simultaneuously increasing the hashmap value by 1.\nFor a given presum, if presum-target exists in the hash, we increase the ans count by the value of hash[presum-target]\n\nNote: We don\'t increment the presum variable and instead assign it directly since our 2d dp already accounts for the prefix sum up until that point! \n\n```\nclass Solution:\n    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:\n        \n        if len(matrix)>len(matrix[0]):\n            new=[[0]*len(matrix) for i in range(len(matrix[0]))]\n            for i in range(len(matrix)):\n                for j in range(len(matrix[0])):\n                    new[j][i]=matrix[i][j]\n            return self.numSubmatrixSumTarget(new,target)\n\n\n        self.dp=[[0]*(len(matrix[0])+1)for i in range(len(matrix)+1)]\n        for i in range(1,len(matrix)+1):\n            for j in range(1,len(matrix[0])+1):\n                self.dp[i][j]=self.dp[i][j-1]+self.dp[i-1][j]-self.dp[i-1][j-1]+matrix[i-1][j-1]\n        \n        ans=0\n        for row1 in range(len(matrix)):\n            for row2 in range(row1,len(matrix)):\n                pres=0\n                myhash={0:1}\n                for col1 in range(len(matrix[0])):\n                        presum=self.dp[row2+1][col1+1]-self.dp[row1][col1+1]\n                        if presum-target in myhash:\n                            ans+=myhash[pres-target]\n                        myhash[pres]=myhash.get(pres,0)+1\n                        \n        return(ans)\n        \n```
['Dynamic Programming', 'Python']