又见台阶

最优解

考虑动态规划
用表示牛牛到第层的方案数，则
等于所有的和，满足：
因此可以使用f数组的奇数项的前缀和和偶数项的前缀和进行转移。
因为f数组中需要的只是的值，所以f值可以在计算的过程中只用临时变量存储。实际存储的值是和，其中表示所有i为偶数的的和,表示所有i为奇数的的和，那么实际上就等于。
对于积水的台阶，因为保证a是以升序给出，所以用一个指针维护下一个积水的台阶就可以不使用额外空间去记录积水台阶了。
空间复杂度，时间复杂度

int solve(int n, int m, vector<int>& a) {
        int mod = 1e9 + 7;
        int dp[2] = {1, 0};
        int p = 0;
        for(int i = 1; i <= n; ++i){
            if(p < m && a[p] == i) {p++; continue; }
            if(i == n) return dp[(i-1)%2];
            dp[i%2] = (dp[i%2] + dp[(i-1)%2])%mod;
        }return 0;
    }