【每日算法Day 96】有限制地跳台阶

题目描述

输入n级台阶（n >= 1），你一次可以跳1级，也可以一次跳2级，但是不能连续跳两级，请问跳到第n级一共有多少种跳法？

示例

输入：3
输出：3
解释：你可以按照（1，1，1）、（2，1）和（1，2）这三种方式跳到第三级

输入：4
输出：4
解释：你可以按照（1，1，1，1）、（2，1，1）、（1，2，1）和（1，1，2）这四种方式跳到第4级，注意（2，2）是不允许的

解题思路

由于不能连续跳2次，所以我们要把dp数组拆分开，使用dp0[i]表示最后一次是跳跃了1级到达第i个位置的跳法种数，用dp1[i]表示最后一次是跳跃了2级到达第i个位置的跳法种数。那么要走一步到达第i个位置，可以从dp0[i - 1]和dp1[i - 1]的和得到种数；要走两步到第i个位置，只能从i-2处上一次是走一步的情况出发，即dp1[i] = dp0[i - 2]。最后dp0[n] + dp1[n]就是到达第n级台阶的总共走法数量。

public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    while (in.hasNextInt()) {
        int n = in.nextInt();
        if(n <= 2){
            System.out.println(n);
            continue;
        }
        //dp0[i]表示从i-1走一步到第i个位置的走法，dp1[i]表示从从i-2走两步步到第i个位置的走法
        //在状态转移时，要到达第i个位置，有两种途径，一是从第i-1个位置走1步，一是从第i-2个位置走两步
        long[] dp0 = new long[n + 1], dp1 = new long[n + 1];
        dp0[0] = 1;
        dp0[1] = 1;
        dp1[1] = 0;
        for(int i = 2; i <= n; i++){
            dp0[i] = dp0[i - 1] + dp1[i - 1];
            dp1[i] = dp0[i - 2];
        }
        long ans = dp0[n] + dp1[n];
        System.out.println(ans);
    }
}