Simple and Clear 2ms Solution in C++ Without Recursion


  • 17
    C
    class Solution {
    public:
        int climbStairs(int n) {
            int StepOne = 1;
            int StepTwo = 0;
            int ret = 0;
            for(int i=0;i<n;i++)
            {
                ret = StepOne + StepTwo;
                StepTwo = StepOne;
                StepOne = ret;
            }
            return ret;
        }
    };
    

    This problem is a Fibonacci problem.
    F(n)=F(n-1)+F(n-2);
    Solving this problem by recursion ,we will do a lot of same recursion.
    Example:
    F(10)=F(9)+F(8);
    F(9)=F(8)+F(7);
    we calculate F(8) twice,when n is large,this will increase as a rate of n's exponent.

    So a more efficient way to solve this problem is from Bottom to Top.
    Calculate F(0) ,F(1);
    then F(2).........


Log in to reply
 

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