public class Solution {
public int climbStairs(int n) {
if(n==1) return 1;
if(n==2) return 2;
return climbStairs(n-1)+climbStairs(n-2);
}
}
It exceeds the time limit because this recursive formula for finding the nth fibonacci number results in an exponential runtime of order n, which is more or less as bad as it gets. You're right, if you use an array to store previous values as you compute them, you can get the runtime to be linear. Note that you only need an array of length two in order to do this.