import java.util.Date;
/**
* 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
* 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
* 注意：给定 n 是一个正整数。
**/
class Main {
public static void main(String[] args) {
System.out.println("Hello World!");
climbStairs(90);
}
public static long climbStairs(int n) {
long[] cache = new long[n];
long start = new Date().getTime();
long sum = calcN(n, cache);
System.out.println("time: " + (new Date().getTime() - start));
System.out.println("sum: " + sum);
System.out.println("");
for(int i=0; i<n; i++){
System.out.println(String.format("[%3d]: %d", i+1, cache[i]));
}
return sum;
}
public static long calcN(int n, long[] cache){
if(cache[n-1] != 0){
return cache[n-1];
}
if(n <= 1){
cache[0] = 1;
return 1;
}else if( n == 2){
cache[1] = 2;
return 2;
}else{
long ret = calcN(n-1, cache) + calcN(n-2, cache);
cache[n-1] = ret;
return ret;
}
}
}
