又见台阶

一共又n层台阶有些台阶上有积水，牛牛一开始在第0层，它每次可以跳奇数层台阶，他想跳到第n曾，但他不想在跳跃的过程中跳到有积水的台阶，现在已知有m个台阶上有积水，问牛牛在不跳到积水台阶的情况下跳到第n层有多少种跳法， 答案对取模

案例
输入：9,3,[1,3,5]
返回值：2
说明：
因为1，3，5都不能走，所以第一步可以跳到第7层或者第9层
所以一共两种方案：

1. 第一步跳7，第二步跳1，第三步跳1
2. 第一步跳9

方法一 模拟

遍历所有台阶对于第i个有3种情况

• 如果台阶上有积水，则跳过当前台阶不统计当前台阶的次数
• 如果台阶上没有积水，且当前的台阶是奇数，则当前台阶的次数最少为1因为可以直接从0跳到当前台阶，并加上前面所有偶数台阶的次数，因为可以从偶数台阶跳奇数次跳到奇数台阶
• 如果台阶上没有积水，且当前的台阶是偶数，则与奇数次相反，把前面所有奇数的台阶次数加起来，因为跳到偶数台阶的情况只有一种就是上一次的台阶是奇数阶，奇+奇=偶

class Solution {
public:
    long long dp[100010];
    long long  mod = 1e9 + 7;
    int solve(int n, int m, vector<int>& a) {
        // write code here
        dp[0] = 1;
        int id = 0;
        for(int i = 1; i <= n; i ++){
           if(id < m && a[id] == i){ //如果遇到积水的格子则跳过
               id ++; continue;
           }
           int t = 1;
           while(i - t >= 0){ //把前面所有能踩到的格子加起来
               dp[i] += dp[i - t];
               dp[i] %= mod;
               t += 2;
           }
           dp[i] %= mod;
        }
        return dp[n] % mod;
    }
};

时间复杂度: 遍历所有的台阶i，对于i台阶会使用 次去统计答案所以总复杂度为
空间复杂度: dp数组统计每一位到的方案数,最多会记录n个台阶的方案数

方法二 迭代

主要的思想和方法一一样类似对方法一加了优化，定义两个变量一个存储奇数台阶odd的总方案数一个存储偶数台阶even的总方案数，当遍历到第i个台阶时如果当前台阶是奇数台阶则将更新为答案，并且将奇数变量加上当前的答案，偶数则相反

class Solution {
public:
    long long mod = 1e9 + 7;
    int solve(int n, int m, vector<int>& a) {
        if(a[m - 1] == n) return 0;
        long long odd = 0, even = 0;
        int id = 0, ans;
        for(int i = 1; i <= n; i ++){
            if(id < m && a[id] == i){
                id ++; continue;
            }
            if(i % 2) { //为奇数时说明当前的方案数一定+1并且选取前面偶数为的所有方案数
                ans = 1 + even;
                odd += even + 1;
            }else{ //偶数相反 将前面奇数位加起来
                ans = odd;
                even += odd;
            }
            odd %= mod; even %= mod; ans %= mod;
        }
        return ans;
    }
};

时间复杂度: 只需要遍历一遍n即可
空间复杂度: 只使用若干个变量