LC70. Climbing Stairs

Basically Fibonacci. But in this case. F(1) = 1, F(2) = 2 and F(n) = F(n – 1) + F(n – 2)

<br />    int climbStairs(int n) {
        if (n <=2)
            return n;

        std::vector<int>steps(n + 1, 0);
        steps[1] = 1;
        steps[2] = 2;
        for(int i = 3; i < steps.size(); i ++){
            steps[i] = steps[i - 1] + steps[i - 2];
        }
        return steps[steps.size() - 1];
    }

Memory

Since we only need two ints before us to figure the current ans. We don’t need the vector.

    int climbStairs(int n) {
        if (n <=2)
            return n;


        int stepFurther = 1;
        int stepCloser = 2;
        int curStep = 0;
        for(int i = 3; i <= n; i ++){
            curStep = stepFurther + stepCloser;
            stepFurther = stepCloser;
            stepCloser = curStep;

        }
        return curStep;
    }

For loop’s size

Pay close attention for i <= n. Since our base case starts at 0 and the answer is at n. So we actually need to step forward n + 1 times.

Leave a Reply

Your email address will not be published. Required fields are marked *

To create code blocks or other preformatted text, indent by four spaces:

    This will be displayed in a monospaced font. The first four 
    spaces will be stripped off, but all other whitespace
    will be preserved.
    
    Markdown is turned off in code blocks:
     [This is not a link](http://example.com)

To create not a block, but an inline code span, use backticks:

Here is some inline `code`.

For more help see http://daringfireball.net/projects/markdown/syntax