Classical iterative solution


  • 0
    C
    class Solution {
    public:
        int climbStairs(int n) 
        {
            // f(n) = f(n-1) + f(n-2)
            // f(0) = 0, f(1) = 1, f(2) = 2
            
            if(n <= 0) return 0;
            if(n <= 2) return n;
            
            int f_n;
            int f_n_1 = 2, f_n_2 = 1;
            for(int i=3; i <= n; i++)
            {
                f_n = f_n_1 + f_n_2;
                f_n_2 = f_n_1;
                f_n_1 = f_n;
            }
            
            return f_n;
        }
    };

Log in to reply
 

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