Climbing Stairs

PROBLEM

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?

Example1

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

Example2

*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

SOLVING

We’ll use Dynamic Programming method and more specifically the memoization method.

From a certain way we can see this problem like a Fibonnacy problem. Because we want to substract 1 or 2 until we reach 0 Like the Fibonnacy where n equal n-1 + n-2

Steps

• Return 1 if target is inferior to 2
• If the target already in memo use it
• memo[target] equal the method with target-1 plus target-2
• Return the value in the memo

Code

class Solution {
public:
  int climbStairs(int n) { return dynamic(n); }

private:
  map<int, int> memo;

  int dynamic(int target) {
    if (target < 2)
      return 1;

    if (memo[target])
      return memo[target];

    memo[target] = dynamic(target - 1) + dynamic(target - 2);
    return memo[target];
  }
};

• DYNAMICPROGRAMMING
• PROBLEM