枚举

​ 枚举就是尝试所有的可能性，尤其是当我们在确定一个问题是不是的这一类问题中尤其有用，例如说给一堆数，让我我们判断他们是不是素数，或者素数的数量的时候，这里他们就是判断类问题我们就可以使用枚举。

​ 但是注意这里我们需要考虑的就是枚举的方式，也就是枚举的角度。这里有一个小的例子就是最长回文子串的问题。

​ 首先我们就是用一个最简单的方式就是枚举出所有的字串，然后在这些字串里面找回文串。这样我们首先需要进行枚举就需要 n 平方的复杂度，然后我们还需要 n 的时间去判断这个串是不是回文，那么也就是说我们需要 n 三次方的时间复杂度。

​ 然后上面的方式枚举的对象就是所有的字串，但是我们仔细就会发现重点在于回文子串的中心，如果我们枚举的是回文子串的中心以及回文的长度，我们就更简单的找到最长回文子串。中心不仅仅就是每一个字符还包括他们之间的缝隙，这样我们就有了 2n + 1 个中心，然后在对他们进行回文判断，最后的时间复杂度也就是 n 平方。

​ 这里是从 n 三次方降到了 n 平方的复杂度，这样的原因在于我们去掉了很多的无用的字串，第一个枚举的方法就是枚举所有的字串，然后第二个就是仅仅找出那些具有回文形式的字串，这样就少了一个 n 。经常这样思考会慢慢锻炼我们优化时间复杂度的能力。

​ 并且这里看着是 n 平方其实他根本没有那么多的复杂度，因为每一个中心能找到的会问其实并不多除非我们给的一个串是一个完全相同的字符，这也就是第二种算法的最坏情况。

​ 其实在枚举的过程中有的枚举并没有必要，因为这些就是用来占用了时间复杂度但是没有给程序带来多大的帮助。然后我们在计算的时候有时候题目给的条件很少，这时候我们就需要使用枚举来增加我们已知的条件。

​ 再看一个例子就是在一个矩阵中填满数，然后这些数有正有负我们需要获取一个和的最大矩阵。这里我们先不考虑 DP 而是使用枚举的方式来解这道题。因为这道题的内容是静态的，也就是矩阵是不变化的，我们可以使用计算存储，然后再使用排容原理解题。首先我们考虑一维的情况，我们可以新开一个矩阵，这个矩阵的目的就在于把原来的矩阵的到当前位置的和记录下来。这样我们仅仅需要一次的扫描就能获取从 0 到当前位置的和，然后我们可以计算出任何两个点的之间的和，使用排容原理，就是后面的下标的和减去前面的下标的和即可。这样一个最大的和我们就可以使用 n 的复杂度完成。

​ 然后我们扩展到二维的情况，就是新开一个矩阵，然后每一个位置记录 ( 0 , 0 ) 位置到当前位置的和。至于这个和怎么算还需要一个过程，中间我们还需要构造一个矩阵，这个矩阵就是先计算出每一行的和，也就是我们上面所说的一维的情况，然后再过渡到二维的辅助阵列。

​ 那么这个算法的复杂度就是一开始我们需要算出这个辅助矩阵的和需要 n 平方的时间，然后需要进行排容原理，也就是我们要枚举左上角和右下角的位置这里就需要 n 的四次方的时间。

​ 但是这样做还是不够好，也就是我们枚举了每一个矩形，我们只是优化了 计算矩形的和。但是我们可以使用另外一种思路就是枚举左右边界，然后我们计算出上下界，这样的话这里的时间复杂度就是 n 平方乘以我们算出上下界的时间。而我们算上下界的时候因为我们已经指定了宽度所以说这个宽度之间的东西我们可以把它影射成一维的解决即可。