题解 | #又见台阶#

题意整理

总共有n层台阶，起初牛牛在第1层。
牛牛每次能跳奇数层台阶，问有多少种不同的跳法到达第n层台阶（不能踩到积水的台阶）。

方法一（记忆化递归）

1.解题思路

递归终止条件：只有0层或1层的时候，共1种方案，返回1。
递归如何推进：当前层的方案数，需要借助之前所有相隔奇数层的方案数来计算，即 $cnt=cnt+dfs(n-i,m,a)$ （i的范围在1到n，并且总是奇数）。
每一层递归返回什么：当前层的方案数。

由于递归会有很多重复的计算，可以通过记忆数组记录之前计算过的状态。

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @param m int整型 
     * @param a int整型一维数组 
     * @return int整型
     */
    //声明记忆数组
    int[] memo;
    //声明标记数组
    boolean[] w;
    //声明取余常数
    int mod=1000000007;

    public int solve (int n, int m, int[] a) {
        //初始化
        memo=new int[n+1];
        w=new boolean[n+1];
        Arrays.fill(memo,-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(memo[n]!=-1) return memo[n];
        //如果标记为积水，直接返回0
        if(w[n]){
            memo[n]=0;
            return 0;
        } 
        //递归终止条件
        if(n==0||n==1) return 1;
        int cnt=0;
        //统计相隔奇数层的情况，并累加
        for(int i=1;i<=n;i+=2){
            cnt=(cnt+dfs(n-i,m,a))%mod;
        }
        memo[n]=cnt;
        return cnt;
    }
}

3.复杂度分析

时间复杂度：递归的层数为n，递归里面还嵌套着一个循环，所以时间复杂度是 $O(n^2)$ 。
空间复杂度：需要额外深度为n的递归栈，同时需要大小为n+1的记忆数组和标记数组，所以空间复杂度是 $O(n)$ 。

方法二（迭代）

1.解题思路

简要分析：由于牛牛每次可以跳奇数层台阶，假设当前层是第n层， $f[n]$ 表示跳到第n层的方案数，很容易得出 $f[n]=f[n-1]+f[n-3]+……+f[n-i]$ ，其中 $n-i>=0$ 。如果n是奇数，那么当前方案数是之前所有偶数层方案数累加和，如果n是偶数，那么当前方案数是之前所有奇数层方案数累加和。所以我们只需要用两个变量分别记录奇数层和偶数层的累加和就行了。

初始化odd和even两个变量，odd为之前层的奇数层方案累加和，even为之前层的偶数层方案累加和。
如果当前层有积水，则跳过。
如果是奇数层，利用even跟新odd；如果是偶数层，利用odd跟新even。
计算返回值时，如果是积水层，直接返回0。如果是奇数层，返回even，如果是偶数层，返回odd。

动图展示：
图片说明

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @param m int整型 
     * @param a int整型一维数组 
     * @return int整型
     */
    //取余常数
    int mod=1000000007;

    public int solve (int n, int m, int[] a) {
        //odd为之前层的奇数层方案累加和，even为之前层的偶数层方案累加和
        int odd=0,even=1,id=0;

        for(int i=1;i<=n;i++){
            //如果当前层有积水，则跳过
            if(id<m&&a[id]==i){
                id++;
                continue;
            }
            //如果是奇数层，则可以由之前层的偶数层方案累加和得到
            if(i%2==1){
                odd=(odd+even)%mod;
            }
            //如果是偶数层，则可以由之前层的奇数层方案累加和得到
            else{
                even=(even+odd)%mod;
            }
        }

        for(int w:a){
            if(w==n) return 0;
        }
        //如果n为奇数，方案数等于之前层的偶数层方案累加和，反之则是之前奇数层累加和
        return n%2==1?even:odd;
    }

}

3.复杂度分析

时间复杂度：第一个循环最多执行n次，第二个循环最多执行m次，m总小于等于n，所以时间复杂度是 $O(n)$ 。
空间复杂度：需要额外常数级别的空间，所以空间复杂度是 $O(1)$ 。