yokolet's notelets

  1. Dynamic Programming
  2. Climbing Stairs

Dynamic Programming

Climbing Stairs

Problem Description

You are climbing a staircase. It takes n steps to reach the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Constraints:

  • 1 <= n <= 45

https://leetcode.com/problems/climbing-stairs/

Examples

Example 1
Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps
Example 2
Input: n = 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

How to Solve

This is a well-known problem. The DP (dynamic programming) and recursion are common approaches. The DP approach can simplify the solution by considering the problem as a fibonacci sequence. The sequence is: step(n) = step(n - 1) + step(n - 2). Starting from two states, previous of previous and previous, repeat adding those gives the answer.

Solution

  • class ClimbingStairs {
    public:
        int climbStairs(int n) {
            if (n <= 2) { return n; }
            int prevprev = 1, prev = 2, cur = 0;
            for (auto i = 2; i < n; ++i) {
                cur = prevprev + prev;
                prevprev = prev;
                prev = cur;
            }
            return cur;
        }
    };
    
  • class ClimbingStairs {
        public int climbStairs(int n) {
            if (n <= 2) { return n; }
            int prevprev = 1, prev = 2, cur = 0;
            for (int i = 2; i < n; ++i) {
                cur = prevprev + prev;
                prevprev = prev;
                prev= cur;
            }
            return cur;
        }
    }
    
  • /**
     * @param {number} n
     * @return {number}
     */
    var climbStairs = function(n) {
        if (n <= 2) { return n; }
        let prevprev = 1, prev = 2, cur = 0;
        for (let i = 2; i < n; i++) {
            cur = prevprev + prev;
            prevprev = prev;
            prev = cur;
        }
        return cur;
    };
    
  • class ClimbingStairs:
        def climbStairs(self, n: int) -> int:
            if n <= 2:
                return n
            prevprev = 1
            prev = 2
            cur = 0
            for i in range(2, n):
                cur = prevprev + prev
                prevprev, prev = prev, cur
            return cur
    
  • # @param {Integer} n
    # @return {Integer}
    def climb_stairs(n)
        if n <= 2
            return n
        end
        prevprev, prev, cur = 1, 2, 0
        (2...n).each do |_|
            cur = prevprev + prev
            prevprev = prev
            prev = cur
        end
        return cur
    end
    

Complexities

  • Time: O(n)
  • Space: O(1)
Easy
Dynamic Programming
Memoization