题解 | #又见台阶#

题目描述
台阶一共有n层，有一些台阶上有积水。

牛牛一开始在第0层，它每次可以跳奇数层台阶，他想跳到第n层，但是它不希望在跳跃的过程中踩到积水。

已知有m个台阶上有积水。
请问牛牛在不踩到积水的情况下跳到第n层有多少种不同的方案。如果不可能到达第n层，则答案为0。

为了防止答案过大，答案对1e9+7取模。

方法一：递归求解

求解思路
对于本题目的求解，由于当前层的方案数和前一层有关，因此我们想到使用递归的方法进行求解，根据上述思想，我们即可得到本问题的解答。递归公式如下图展示。

图片说明

解题代码

import java.util.*;
public class Solution {
    int[] memory;
    boolean[] w; // 存储积水的位置
    public int solve (int n, int m, int[] a) {
        memory=new int[n+1]; // 初始化数组
        w=new boolean[n+1];
        Arrays.fill(memory,-1);
        for(int i=0;i<m;i++)
        {
            w[a[i]]=true;
        }
        return dfs(n,m,a);
    }
    private int dfs(int n, int m, int[] a)
    {
        if(memory[n]!=-1) return memory[n];
        if(w[n])
        {
            memory[n]=0; // 这个地方有积水
            return 0;
        } 
        if(n==0||n==1) return 1;
        int count=0; // 存储方案数
        for(int i=1;i<=n;i+=2)
        {
            count=(count+dfs(n-i,m,a))%1000000007; // 更新结果
        }
        memory[n]=count;
        return count; // 返回方案数
    }
}

复杂度分析
时间复杂度：n次递归，并且每次递归的时间复杂度为 $O(N)$ ，因此时间复杂度为 $O$ ( $图片说明$ )
空间复杂度：使用memory[n],因此空间复杂度为 $O(N)$

方法二：迭代思想求解

求解思路
对于本题目的求解，我们可以将积水分为在奇数层和偶数层来分别讨论。在进行方案累加过程中，如果当前层有积水，则跳过当前层。如果没有积水则进行方案的累加。同时对奇数层和偶数层分别进行讨论，这样根据上述思路即可得到本问题的答案。

图片说明

解题代码

import java.util.*;
public class Solution {
    public int solve (int n, int m, int[] a)
    {
        //odd为之前层的奇数层方案累加和，even为之前层的偶数层方案累加和
        int onum=0,evnum=1,id=0;
        for(int i=1;i<=n;i++)
        {
            if(id<m&&a[id]==i)
            {   //积水层，跳过
                id++;
                continue;
            }
            if(i%2==1)
            {   // case odd
                onum=(onum+evnum)%1000000007;
            }
            else
            {   // case even
                evnum=(evnum+onum)%1000000007;
            }
        }
        for(int w:a)
        {
            if(w==n) return 0;
        }
        return n%2==1?evnum:onum; // 返回结果
    }
}

复杂度分析
时间复杂度：一层循环，因此时间复杂度为 $O(N)$
空间复杂度：常数级内存空间，因此空间复杂度为 $O(1)$