扫雷MINE（枚举+递推）

此类题型往往枚举量有限，剩下部分可以依靠有效的递推解决问题

//枚举优化，注意到只要确定了第一个空的状态，第二空的状态也是定的，以此类推，只要看最后一个空是否合理就行 
#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;
}