扫雷MINE（枚举优化）

枚举的要点：

确定需要枚举的变量

确定枚举的范围

优化手段 ：改变/减少枚举变量

缩小枚举范围

二分 ：二分查找、二分搜索非常有效，一般是复杂度从O(N)降到O(logN)，使用范围也很广

哈希：Hash，空间换时间

双指针：Leetcode上对应的分类是two pointer，直译过来就是双指针，大概的思想就是滑动窗口

前缀、后缀和：空间换时间

//枚举优化，注意到只要确定了第一个空的状态，第二空的状态也是定的，以此类推，只要看最后一个空是否合理就行 
#include <bits/stdc++.h>
using namespace std;
int arr[10005];//存输入的数据
int res[10005];//存方案
int n,cnt=0;//计数多少种方案 
bool check()//通过arr最后一个数，检查扫雷的第一列是否合理 
{
    if(arr[n] - res[n] - res[n-1] == 0)    return true;
    else return false;
}
void dfs(int pos)//用了搜索的板子写枚举 
{
    int i, j, k;
    if(pos == n + 1)//当最后一个空填完后，检查 
    {
    if(check()) cnt++;//如果合理，计数+1 
    return ;
    }
    res[pos] = arr[pos - 1] - res[pos - 1] - res[pos - 2];//每个位置是否有雷，等于右上角的数字减去上面两个空的雷数 
    if(res[pos] < 0) return; //如果出现负数，直接排除 
    dfs(pos + 1);//搜索下一位
}
int main()
{
    int i;
    cin>>n;
    for(i=1;i<=n;i++)   
        scanf("%d", &arr[i]);
    res[1] = 0;
    dfs(2);//若第一个位置无雷 
    memset(res,0,sizeof(res));//清空记录 
    res[1] = 1;
    dfs(2);//若第二个位置有雷 
    cout<<cnt<<endl;
    return 0;
}