目录
-
- 1. 前缀和数组的递推公式: dp[i][j] = dp[i-1][j] + dp[i][j-1] + nums[i][j] - dp[i-1][j-1].
- 2. 前缀和数组需要额外开一行一列.
- 3. 想要快速求任意一个矩形和, 实际上是多个前缀和的拼凑.
今天来贴一道模板题 -> 二位前缀和
然后我们来简单总结两个公式:
因为这是一个 [模板题] 嘛, 所以我们重点说两个问题
- 前缀和数组如何求解?
- 如何利用前缀和数组?
1. 前缀和数组的递推公式: dp[i][j] = dp[i-1][j] + dp[i][j-1] + nums[i][j] - dp[i-1][j-1].
原理很简单, 我们可以看下面图:
我们以虚线和实线对图形进行分割, 实际上我们可以区分出A, B, C, D四大块来. 我们的dp[i, j]想要代表的是A + B + C + D区域的大小.
所以我们可得公式: dp[i][j] = dp[i-1][j] + dp[i][j-1] + nums[i][j] - dp[i-1][j-1].
2. 前缀和数组需要额外开一行一列.
显然, 我们根据上面公式, 当i = 0 或 j = 0的时候, 肯定会越界, 所以我们需要额外开一行一列来避免这种情况(当然进行特殊判断也可以).
3. 想要快速求任意一个矩形和, 实际上是多个前缀和的拼凑.
比如, 我想要求下面这个图的矩形和:
所以我们可以得到利用二维前缀和的公式是: ret = dp[i][j] - dp[i-1][j] - dp[i][j-1] + dp[i-1][j-1].
参考代码是:
int main(
