[LeetCode] 0070 Climbing Stairs

Climbing Stairs

LeetCode - 0070 Climbing Stairs
https://leetcode.com/problems/climbing-stairs/

Problem Description

You are climbing a stair case. It takes n steps to reach to the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Note: Given n will be a positive integer.

Example 1:

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

Example 2:

Input: 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

Solutions

Recursion

int recursion(int n){
    if(n < 0) return 0;
    if(n < 3) return n;
    return recursion(n-1) + recursion(n-2);
}

Dynamic Programming

int dynamicProgramming(int n){
    if(n < 0) return 0;
    if(n < 3) return n;
    int sol[n+1] = {};
    sol[1] = 1;
    sol[2] = 2;
    for(int i = 3; i < n+1; i++)
        sol[i] = sol[i-1] + sol[i-2];

    return sol[n];
}

• Time complexity: O(n)
• Space complexity: O(n)

Fibonacci

int fibonacci(int n){
  if(n < 0) return 0;
  if(n < 3) return n;
  int sol = 0, one_step_b4 = 2, two_steps_b4 = 1;
  for(int i = 3; i < (n+1); i++){
      sol = one_step_b4 + two_steps_b4;
      two_steps_b4 = one_step_b4;
      one_step_b4 = sol;
  }
  return sol;
}

• Time complexity: O(n)
• Space complexity: O(1)