P1255 数楼梯 | JAVA题解

题目解题说明AC代码

我们由题可知 影响第n个阶梯的走法数量与n-1和n-2个阶梯的数量决定，然后以此类推，得到递推公式。
f(n-1)+f(n-2)=f(n)
这里因为数据的问题，5000 那么递归的时间复杂度爆炸，所以我们可以用备忘录的方法来解决（也就是用一个数组去存已经获取到的值，以便于不重复获取）。
这里还有一个点！！！数据量太大，所以需要高精度处理。

代码如下：

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

public class P1255 {
    private static BigInteger[] memo;
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int N=sc.nextInt();
        BigInteger bigInteger=new BigInteger("0");
        memo=new BigInteger[N+1];
        for (int i = 0; i < memo.length; i++) memo[i]=new BigInteger("0");
        System.out.println(helper(N));

    }
   static BigInteger helper(int N){
        if(N<2){
            return new BigInteger("1");
        }
        if(memo[N].compareTo(new BigInteger("0"))==1) return memo[N];
        memo[N]=helper(N-1).add(helper(N-2));
        return memo[N];
   }

}