变态跳台阶

题目来源：牛客网--变态跳台阶

题目描述

一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

解题思路

还是斐波那契数列的变种，只不过不再局限于fn = f(n-1) + f(n-2)
规律变成了fn = f(n-1) + f(n-2) + ... + f1 + 1
最后加一，是一下跳 n 阶的一种情况。

java 代码

import java.util.Scanner;

/**
 * 变态跳台阶   一次可以跳一个、两个、。。。。n个台阶
 * @author jiayanzhao
 * 2019年7月22日
 */
public class superJumpSteps {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int[] fsequence = new int[32];
        fsequence[1] = 1;
        fsequence[2] = 2;
        for (int i = 3; i < 32; i++) {
            // fn = f(n-1) + f(n-2) + ... + f1
            for (int j = i-1; j > 0; j--) {
                fsequence[i] += fsequence[j];
            }
            // 每次都加一，一下跳到 i 阶台阶
            fsequence[i] += 1;
        }
        int n = in.nextInt();
        System.out.println(fsequence[n]);
        in.close();
    }
    
}