给定一个二维矩阵，计算其子矩形范围内元素的总和，该子矩阵的左上角为 (row1, col1) ，右下角为 (row2, col2)。
上图子矩阵左上角 (row1, col1) = (2, 1) ，右下角(row2, col2) = (4, 3)，该子矩形内元素的总和为 8。
示例:
给定 matrix = [ [3, 0, 1, 4, 2], [5, 6, 3, 2, 1], [1, 2, 0, 1, 5], [4, 1, 0, 1, 7], [1, 0, 3, 0, 5] ] sumRegion(2, 1, 4, 3) -> 8 sumRegion(1, 1, 2, 2) -> 11 sumRegion(1, 2, 2, 4) -> 12
说明:
- 你可以假设矩阵不可变。
- 会多次调用 sumRegion 方法。
- 你可以假设 row1 ≤ row2 且 col1 ≤ col2。
**难度**: Medium
**标签**: 动态规划、
# -*- coding: utf-8 -*-
# @Author : LG
"""
执行用时：128 ms, 在所有 Python3 提交中击败了92.83% 的用户
内存消耗：16.9 MB, 在所有 Python3 提交中击败了29.48% 的用户
解题思路：
动态规划
计算 左上角到某一点的 和
计算两点之间的和时， 等于右下角点到原点的和 - 上侧 - 左侧 + 左上角到原点的和
"""
class NumMatrix:
def __init__(self, matrix: List[List[int]]):
if matrix and matrix[0]:
self.m = len(matrix)
self.n = len(matrix[0])
self.dp = [[0 for _ in range(self.n+1)] for _ in range(self.m+1)]
for i in range(1, self.m+1):
for j in range(1, self.n+1):
self.dp[i][j] = self.dp[i-1][j] + self.dp[i][j-1] - self.dp[i-1][j-1] + matrix[i-1][j-1]
def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
if self.m == 0 or self.n == 0:
return 0
# print(self.dp)
row1, col1, row2, col2 = row1+1, col1+1, row2+1, col2+1
# print(self.dp[row2][col2], self.dp[row1-1][col1], self.dp[row1][col1-1], self.dp[row1-1][col1-1])
return self.dp[row2][col2] - self.dp[row1-1][col2] - self.dp[row2][col1-1] + self.dp[row1-1][col1-1]
