I was interviewed this problem, came up with the Fibonacci method but didn't find the stack solution


  • 0
    K

    Fibonacci using cache

    public class Solution {
         static int[] arr = new int[35535];
                    
         public int climbStairs(int n) {
              if(arr[n] != 0) return arr[n];
              if(n < 3)
              {
                   arr[n] = n;
                   return n;
              }
              int res = climbStairs(n-1) + climbStairs(n-2);
              arr[n] = res;
              return res;
          }
    }
    

    Using Stack

    public class Solution {
        public int climbStairs(int n) {
            if(n < 3) return n;
            Stack<Integer> st = new Stack<Integer>();
            
            st.push(new Integer(1));
            st.push(new Integer(2));
            
            int i = 3;
            while(i <= n){
                Integer a = st.peek();
                st.pop();
                Integer b = st.peek();
                st.push(a);
                st.push(new Integer(a.intValue() + b.intValue()));
                i++;
            }
            return st.peek().intValue();
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.