跳楼梯（洛谷P1255题题解，Java语言描述）

题目要求

题目链接

分析

一个经典问题，跳楼梯问题，考察最最最简单的DP。

从当前阶梯看，可以向上跳1格或是2格（前提是受到顶部约束）；倒过来看，从起点到达当前阶梯的可能路径数是从起点到当前阶梯-1和当前阶梯-2的可能路径数之和（受到底部约束），因为只能来自其下的两个阶梯。

所以，写出状态转移方程： f [ i ] = f [ i − 1 ] + f [ i − 2 ] f[i]=f[i-1]+f[i-2] f[i]=f[i−1]+f[i−2]

注意0台阶的情况，此时没有台阶可以跳，所以结果是0； 但非0的时候可以初始化0台阶处为1。

AC代码（Java语言描述）

import java.math.BigInteger;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int num = scanner.nextInt();
        scanner.close();
        if (num == 0) {
            System.out.println(0);
            return;
        }
        BigInteger[] nums = new BigInteger[num+1];
        nums[0] = nums[1] = BigInteger.ONE;
        for (int i = 2; i