Java版爬楼梯递归版最佳优化

假设你现在正在爬楼梯，楼梯有 nn 级。每次你只能爬 11 级或者 22 级，那么你有多少种方法爬到楼梯的顶部？

输入格式

第一行输入一个整数 n(1≤n≤50)n(1≤n≤50)，代表楼梯的级数。

输出格式

输出爬到楼梯顶部的方法总数。

样例输入

5

样例输出

8

关键在于保存每次的计算状态，减少重复计算

import java.util.*;
class Main{
 static int a[];
    public static int f(int k){
        if(k==1||k==0){return 1;}
        if(k>1){
        if(a[k-2]==0){
            a[k-2]=f(k-2);
            return f(k-1)+f(k-2);
        }
        return f(k-1)+a[k-2];}
        return 0;
    }
    public static void main(String[] args) {
        Scanner input =new Scanner(System.in);
        int q=input.nextInt();
        a=new int[q];
        System.out.print(f(q));
    }
}

原文地址：https://blog.csdn.net/a825245794/article/details/72594526?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522168474998616800188596623%2522%252C%2522scm%2522%253A%252220140713.130102334.pc%255Fall.%2522%257D&request_id=168474998616800188596623&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~first_rank_ecpm_v1~rank_v31_ecpm-18-72594526-null-null.142^v87^control_2,239^v2^insert_chatgpt&utm_term=java%E4%BC%98%E5%8C%96