题解 | #又见台阶#

题目：
台阶一共有n层，有一些台阶上有积水。牛牛一开始在第0层，它每次可以跳奇数层台阶，他想跳到第n层，但是它不希望在跳跃的过程中踩到积水。已知有m个台阶上有积水。请问牛牛在不踩到积水的情况下跳到第n层有多少种不同的方案。如果不可能到达第n层，则答案为0。
为了防止答案过大，答案对1e9+7取模。
方法一：迭代
从第0层台阶只能跳奇数层到第奇数层台阶，所以将第0层台阶的方案初始化为1，,将跳到第奇数层台阶的方案和第偶数层台阶的方案分开计算

要跳到第奇数层台阶需要从第偶数层台阶处再跳奇数层，因此，跳到第奇数层台阶的方案数=之前所有跳到第偶数层台阶方案数的累加和
要跳到第偶数层台阶需要从第奇数层台阶处再跳奇数层，因此，跳到第偶数层台阶的方案数=之前所有跳到第奇数层台阶方案数的累加和

如果第n层是水沟，则不可能到达第n层，返回0，如果第n层是奇数则返回之前所有偶数层台阶方案数的累加和，否则，之前返回所有奇数层台阶方案数的累加和

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @param m int整型 
     * @param a int整型一维数组 
     * @return int整型
     */
    public int solve (int n, int m, int[] a) {
        // write code here
        if(a[a.length-1]==n)return 0;//第n层是水沟，直接返回0
        int mod=1000000007;
        int index=0,sum1=0,sum2=1;//初始化奇数层为0，偶数层为1（第0层）
        for(int i=1;i<n;i++){
            if(index<m&&a[index]==i){
                index++;
                continue;//遇到水沟跳过
            }
            if(i%2==0){
                sum2+=sum1;//偶数层=之前的奇数层累加和
                sum2%=mod;
            }
            else if(i%2==1){
                sum1+=sum2;//奇数层=之前的偶数层累加和
                sum1%=mod;
            }
        }
        return (n%2==1)?sum2:sum1;//如果n是奇数，返回之前偶数层累加和，否则返会之前奇数层之和
    }
}

复杂度：
时间复杂度：一重循环， $O(n)$
空间复杂度：常数级额外变量空间， $O(1)$
方法二：记忆化递归
在方法一的分析中，我们得出结论：

$f(n)=f(n-1)+f(n-3)+...+f(0)$ (n为奇数) $f(n)=f(n-1)+f(n-3)+...+f(1)$ (n为偶数)
递归终止条件是n=0或者n=1时， $f(n)=1$
得到自顶向下的递归树
图片说明
如上图所示，由于会出现像 $f(1)$ 这样的重复计算，我们使用一个记忆数组将已经计算过的值存储起来，下一次递归调用到相同值时直接返回结果即可，降低时间复杂度

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @param m int整型 
     * @param a int整型一维数组 
     * @return int整型
     */
    int[]memory;
    boolean[]jump;
    int mod=1000000007;
    public int solve (int n, int m, int[] a) {
        // write code here
        memory=new int[n+1];
        //初始化记忆化数组
        Arrays.fill(memory,-1);
        //需要跳过的积水处初始化为true
        jump=new boolean[n+1];
        for(int i=0;i<m;i++){
            jump[a[i]]=true;
        }
        return f(n);
    }
    int f(int n){
        //如果遇到积水，则记忆数组记录为0，并且直接返回0
        if(jump[n]){memory[n]=0;return 0;}
        //如果已经计算过，则直接返回值
        if(memory[n]!=-1)return memory[n];
        if(n==0||n==1)return 1;//递归终止条件，第0层和第1层的方案数都为1
        int res=0;
        //f(n)=f(n-1)+f(n-3)+...
        for(int i=n-1;i>=0;i-=2){
            res=(res+f(i))%mod;
        }memory[n]=res;//记录进记忆数组
        return res;
    }
}

复杂度：
时间复杂度：递归n次，每次递归的时间复杂度为 $O(n)$ ,总的时间复杂度为 $图片说明$
空间复杂度：额外使用记忆数组和需要跳过积水的数组，空间复杂度为线性, $O(n)$