DP和matrix有关的一切

最好思考一下前后的关系，能不能用已知， 来减小重复计算。

一、 Range Sum Query 2D - Immutable

---

思路

1. 在初始化的时候就生成一个dp数组\矩阵，以后每次访问的时候只要在里面找数就好。
2. 要不要判断边界？

方案

1. 不断累加
   在这里我使用了一个一维数组去记录：

index = i*matrix[0].length + j
dp = dp[i-1] + matrix[index++]

构造dp数组的时候：

int width = matrix[0].lengh;
for(int k=row1; k<=row2; k++)
   if(k*width+col1-1<0)
       sum += dp[k*width+col2];  // 边界检查，还是挺麻烦的
   else
       sum += dp[ k*width+col2] - dp[k*width+col1-1];

2. 切豆腐块
   初始化的时候，可以令边界为0， 从而省去了判断边界。

dp[][] = new int[matrix.length + 1][matrix[0].length + 1]
for(int i=0; i<dp.length; i++)
      matrix[i][0] = 0;
for(int j=0; j<dp[0].length; j++)
      matrix[0][j] = 0;

构造dp矩阵的时候

dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + matrix[i+1][j+1];
// 这里因为dp的大小是matrix的+1,所以下标的处理要注意一下

计算由(row1, col1) 和 (row2, col2)括起来的矩阵的sum：

return ( dp[row2+1][col2+1] - dp[row2+1][col1] -dp[row1][col2+1] + dp[row1][col1] );
// 同样的， 下标的处理要注意一下

参考：http://blog.csdn.net/zdavb/article/details/49807841

小收获

1. 矩阵的动态dp，在某些情况下，可以用加边框的形式，避免了边界检查。p.s.下标的处理要注意一下
2. 多想想怎么以“块”来处理矩阵问题。