差分思想

差分思想：通过关注数据之间的差异来简化问题的求解过程 例题：http://oj.oldmoon.cn/p/1013

方法一

枚举所有可能的杂物清除位置，依次计算答案（能够开垦的荒地块数），选一个最大值。

• 需要枚举最多多少次？
• 每次计算能够开垦的荒地块数，时间复杂度是多少？
• 总时间复杂度是多少？

方法二

能不能更快呢？我们关注到在方法一中，每次计算能够开垦的荒地块数都需要从头开始计算，非常消耗时间。实际上，当我们在1000*1000的矩阵中清楚某处的杂物后，例如(100,100)，只会影响它上下左右和自己最多五处的开垦结果。

所以我们可以先把原矩阵可以开垦的荒地数算出来，假设为x。每次清除完一个杂物后，我们依次判断上下左右和它自己，是否由原来的不能开垦变成了可以开垦，记新增的数量为delta，则清除完该杂物后的可开垦数量为x+delta。因为计算delta的过程非常快，所以极大的提升了时间。

这种对比数据间差异计算结果，而不是从头开始计算的方式，即用到了我们的差分思想。

前缀和数组是不是也用到了差分思想？

试一试

下面的样例数据中，最开始可开垦的荒地数量是多少？

.....
.#..#
.....

当清除(1,1)后，变成了下面的矩阵，此时可开垦的荒地数增加了多少？所以最终可开垦的荒地数为？

.....
....#
.....