304. 前缀和技巧中的边界值处理

题目

题目如下，其实并不难，属于小而美的前缀和技巧中的体型。因为我之前做过这道题，所以重刷也马上就能写。但是对比我写的和之前看别人写的，明显我的代码不够简洁，一个核心的差异在于对DP数组的定义上。

问题

先看下我的代码，我对DP数组的定义是：存储以（0，0）为起点，到（i， j）的数组之和。提交代码显示超出时间限制。

两个问题：

1. 边界条件处理贼麻烦，我自己写的时候也注意到了；(但这不是导致超时的原因)
2. 处理超时，因为我每次要算一遍DP。

class NumMatrix:def __init__(self, matrix: List[List[int]]):self.matrix = matrixdef sumFromLeftCorner(self):R, C = len(self.matrix), len(self.matrix[0])dp = [[0 for j in range(C)] for i in range(R)]for i in range(R):for j in range(C):if i == 0 and j == 0:dp[i][j] = self.matrix[i][j]elif i == 0:dp[i][j] = dp[i][j-1] + self.matrix[i][j]elif j == 0:dp[i][j] = dp[i-1][j] + self.matrix[i][j]else:dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + self.matrix[i][j]return dpdef sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:dp = self.sumFromLeftCorner()if row1 == 0 and col1 == 0:return dp[row2][col2]elif row1 == 0:return dp[row2][col2] - dp[row2][col1 - 1]elif col1 == 0:return dp[row2][col2] - dp[row1 - 1][col2]else:return dp[row2][col2] - dp[row1-1][col2] - dp[row2][col1-1] + dp[row1-1][col1-1]

反思

对于第一个问题：

1. 边界条件处理贼麻烦，我自己写的时候也注意到了；(但这不是导致超时的原因)

只要改一下DP数组的定义即可：存储以（0，0）为起点，到（i-1， j-1）的数组之和。因此DP数组的长宽都要加1；

对于第二个问题：

2. 处理超时，因为我每次要算一遍DP。

将DP数组计算的过程放在__init__下面，总是只计算一次，然后重复调用其结果即可/

修改以后的代码如下，明显简洁很多！

class NumMatrix:def __init__(self, matrix: List[List[int]]):self.matrix = matrixself.dp = self.sumFromLeftCorner()def sumFromLeftCorner(self):R, C = len(self.matrix), len(self.matrix[0])dp = [[0 for j in range(C+1)] for i in range(R+1)]for i in range(1, R+1):for j in range(1, C+1):dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + self.matrix[i-1][j-1]return dpdef sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:return self.dp[row2+1][col2+1] - self.dp[row1][col2+1] - self.dp[row2+1][col1] + self.dp[row1][col1]