题解 | #又见台阶#

思路：

题目的主要信息：

跳上n级台阶，每次只能跳奇数级
a数组中存放着不能跳上的台阶序号
达不到n级就返回0
求跳上n级的方案数，结果需要取模1e9+7

方法一：动态规划
具体做法：
我们可以用动态规划，辅助数组dp，其中 $dp[i]$ 表示i级台阶方法数， $i$ 有如下情况：

如果i级台阶有积水， $dp[i]=0$
如果i为奇数，那它肯定由偶数级台阶跳来，于是 $dp[i]=sum(dp[偶数])$ ，对于每个偶数级台阶跳一个相差的奇数即可
如果i为偶数，那它肯定由奇数级台阶挑来，于是 $dp[i]=sum(dp[奇数])$ ，理由同上

按照上述说法，我们可以计算前缀奇数和与前缀偶数和来辅助dp数组。
图片说明

class Solution {
public:
    int solve(int n, int m, vector<int>& a) {
        int mod = 1e9 + 7;
        vector<int> dp(n + 1, 0); //dp[i]表示i级台阶方法数
        dp[0] = 1;
        int odd = 0; //奇数台阶方法种类前缀和
        int even = 1; //偶数台阶方法种类前缀和
        int index = 0; //记录数组a的下标
        for(int i = 1; i <= n; i++){
            if(i == a[index]){ //积水台阶不算
                index++;
                continue;
            }
            if(i % 2 == 1){ //奇数
                dp[i] = (dp[i] + even) % mod;
                odd = (odd + dp[i]) % mod;
            }
            else{ //偶数
                dp[i] = (dp[i] + odd) % mod;
                even = (even + dp[i]) % mod;         
            }
        }
        return dp[n];
    }
};

复杂度分析：

时间复杂度： $O(n)$ ，遍历一次即可
空间复杂度： $O(n)$ ，辅助数组dp的chang

方法二：递归
具体做法：
按照上述动态规划的思路，依靠前缀奇数和前缀偶数，对于某一个问题，我们可以自顶向下递归地求它的前缀奇数和或者偶数和，以2为遍历基数，将其累加。
图片说明

class Solution {
public:
    int mod = 1e9 + 7;
    int recursion(int n, vector<bool>& water){
        if(water[n]) //有积水
            return 0;
        if(n <= 1)  //不大于1级的方案都是1
            return 1;
        int res = 0;
        for(int i = n - 1; i >= 0; i = i - 2) //求其奇数前缀和或者偶数前缀和
            res = (res + recursion(i, water)) % mod;
        return res;
    }
    int solve(int n, int m, vector<int>& a) {
        vector<bool> water(n + 1, false);
        for(int i = 0; i < m; i++) //标记有水的台阶
            water[a[i]] = true;
        return recursion(n, water);
    }
};

复杂度分析：

时间复杂度： $O(n^2)$ ，递归为 $O(n)$ ，每次累加前缀和也是 $O(n)$
空间复杂度： $O(n)$ ，递归栈深度及辅助数组water的长度