接上文Leetcode10.正则表达式匹配——动态规划之一个模型三个特征。在第17次双周赛的时候，我遇到这么一道题1314. 矩阵区域和。
不过在此，我们先讨论该题的解法的经典题型：
304.二维区域和检索 - 矩阵不可变
给定一个二维矩阵，计算其子矩形范围内元素的总和，该子矩阵的左上角为 (row1, col1) ，右下角为 (row2, col2)。
上图子矩阵左上角 (row1, col1) = (2, 1) ，右下角(row2, col2) = (4, 3)，该子矩形内元素的总和为 8。
注：会多次调用区域求和方法。
拿到该题的时候，看到会多次调用区域求和方法时，就明白不能简单的每次计算区域每一行每一列的数值的和，必然是要保存其中间结果。
考虑到1310. 子数组异或查询，或者子数组求和的题目，我们一目了然，这道题应该用动态规划。
那么怎么去求动态规划方程呢？
首先，我们规定dp[i][j]表示区域(0,0)到(i-1,j-1)的和，dp[1][1]就是(0,0)上点的值，dp[1][2]就是(0,0)加上(0,1)的值，以此类推。
为什么要这样规定呢？而不用dp[0][0]去表示(0,0)的值呢？
因为考虑到for循环是从0开始的，动态规划方程是根据前一个状态来计算的，所以，会导致数组越下界的情况发生。自然的，我们就想到初始化dp数组的时候，将其行列多增加1。
在规定了dp数组的定义后，就可以求解dp方程了。
我们要求解矩阵AD的和，我们手中的dp又是从O点开始计算的，我们唯一能拿到的只有OG、OE、OF、OD四个矩阵的值，自然的就可以得出：
A
D
=
O
D
−
O
E
−
O
F
+
O
G
AD=OD-OE-OF+OG
AD=OD−OE−OF+OG
换成dp数组来表示，就是AD=dp[row2+1][col2+1]-dp[row2+1][col1]-dp[row1][col2+1]-dp[row1][col1]。
结果表示出来了，但是dp数组怎么求还没说呢。
我们可以顺着刚才的思路，把求一个新的dp[i+1][j+1]看成这样：
矩阵AD就相当于新加入的点(i,j)，没错就是把新加入的点看成一个矩阵，那么求解新的OD，就相当于：
O
D
=
A
D
+
O
E
+
O
F
−
O
G
OD=AD+OE+OF-OG
OD=AD+OE+OF−OG
换成dp数组来表示，dp[i+1][j+1]=matrix[i][j]+dp[i+1][j]+dp[i][j+1]-dp[i][j]
所以，我们的代码也就出来了：
class NumMatrix {
int[][] dp;
public NumMatrix(int[][] matrix) {
if (matrix.length == 0 || matrix[0].length == 0) return;
int row=matrix.length;
int col=matrix[0].length;
dp=new int[row+1][col+1];
for(int i=0;i<row;i++){
for(int j=0;j<col;j++){
dp[i+1][j+1]=dp[i][j+1]+dp[i+1][j]+matrix[i][j]-dp[i][j];
}
}
}
public int sumRegion(int row1, int col1, int row2, int col2) {
return dp[row2 + 1][col2 + 1] - dp[row1][col2 + 1] - dp[row2 + 1][col1] + dp[row1][col1];
}
}
/**
* Your NumMatrix object will be instantiated and called as such:
* NumMatrix obj = new NumMatrix(matrix);
* int param_1 = obj.sumRegion(row1,col1,row2,col2);
*/