前缀和是一种动态规划的思想，求的是结果，存的不是结果，而是前缀和，通过前缀和之间运算得到最后想要的结果
前缀和的思想就是：
不存区间结果，从头到当前的节点，减少空间复杂度和初始化的时间复杂度
典型的题目有
- 区域和检索 - 数组不可变
- 二维区域和检索 - 矩阵不可变
303
给定一个整数数组 nums，求出数组从索引 i 到 j（i ≤ j）范围内元素的总和，包含 i、j 两点。
如果用一个数组存每个区间的结果，意思dp[i][j]存从i到j的结果，那么空间复杂度是On^2,太高了，而且初始化dp的时候时间复杂度过高，也是On2
如果dp[i]存前i+1个的总和，那么:
sum(i,j) = dp[j] - dp[i-1]
可以看到，求结果的时间还是O(1),但是省下了一个数量级的空间
304
304是303的升级版，一个是一维前缀和，一个是二维前缀和,这道题用dp[i][j]存从左上角开始到当前节点的前缀和
304的重点就是初始化的时候怎么计算dp[i][j]以及取结果的时候怎么取，题解讲的很好
初始化时
S(O,D)=S(O,C)+S(O,B)−S(O,A)+D
image.png
减去 S(O, A)S(O,A) 的原因是 S(O, C)S(O,C) 和 S(O, B)S(O,B) 中都有 S(O, A)S(O,A)，即加了两次 S(O, A)S(O,A)，所以需要减去一次 S(O, A)S(O,A)。
求结果时
image.png
S(A,D)=S(O,D)−S(O,E)−S(O,F)+S(O,G)
加上子矩形 S(O, G)S(O,G) 面积的原因是 S(O, E)S(O,E) 和 S(O, F)S(O,F) 中都有 S(O, G)S(O,G)，即减了两次 S(O, G)S(O,G)，所以需要加上一次 S(O, G)S(O,G)。
