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));
	}
}