CODEWITHSUNDEEP
algorithmdynamic-programming
Deepesh M
Deepesh M

Reputation: 833

Explain this dynamic programming climbing n-stair code

Problem is

"You are climbing a stair case. Each time you can either make 1 step or 2 steps. The staircase has n steps. In how many distinct ways can you climb the staircase?"

Following is the code solution for this problem but I am having trouble understanding it. Can anybody explain me

int stairs(int n) {
  if (n == 0) return 0;
  int a = 1;
  int b = 1;
  for (int i = 1; i < n; i++) {
    int c = a;
    a = b;
    b += c;
  }
  return b;
 }

Thanks,

Upvotes: 14

Views: 9624

Answers (3)

Marcelo Fern&#225;ndez
Marcelo Fern&#225;ndez

Reputation: 21

In the act of write down the possible options of 1 step, 2 steps to reach a determined floor; For me, somebody saw that the number of combinations was exactly a number into the Fibonacci series. Then, this is the answer. There is a relation between the amount of options (2 options: 1 step, and 2 steps) and the amount of numbers summed to obtain the next number in the Fibonacci series: two numbers. Then if you try to solve a climbing stairs with for example 3 options (1 step, 2 steps, 3 steps) then the result is equivalent to adapt the Fibonacci series but summing 3 numbers, the series will be 0, 1, 1, 2, 4, 7, 13, 24. I don't know if this series has a name but if you check, the result is correct.

Going back to the climbing stairs with 1-2 steps, for the next code, instead of using 3 variables or an array (other solutions that you can find on the web), I'm using an array as a stack. I pop the two previous numbers, calculate the current number in the series, then push the most recent of the previous numbers and then push the current number. These two numbers will be the previous numbers in the next cycle of the while loop.

 /**
 * Using Fibonacci and a stack.
 * @param {number} n
 * @return {number}
 */
const climbingStairs = (n) => {
    if (n === 0) return 0;
    if (n === 1) return 1;
    if (n === 2) return 2;

    let stack = [];
    stack.push(1);
    stack.push(2);
    let current_steps = 3;
    let current_combinations = 0;
    while (current_steps <= n) {
        let previous = stack.pop();
        let previous2 = stack.pop();
        current_combinations = previous + previous2;
        stack.push(previous);
        stack.push(current_combinations);
        current_steps++
    }
    return current_combinations
}

console.log(climbingStairs(5));

Upvotes: 1

Purva
Purva

Reputation: 411

Climbing Stairs Using DP

class Solution {
   public:
     int climbStairs(int n) {
    int dp[n+1];

    if (n <= 1)
        return 1;

    if (n ==2)
        return 2;

    dp[0] = 1;
    dp[1] = 1;
    dp[2] = 2;

    for (int i = 3; i <=n; i++){
        dp[i] = dp[i-1]+dp[i-2];
    }

    return dp[n];
   }};

Upvotes: 0

amit
amit

Reputation: 178431

Well, first you need to understand the recursive formula, and how we derived the iterative one from it.

The recursive formula is:

f(n) = f(n-1) + f(n-2)
f(0) = f(1) = 1

(f(n-1) for one step, f(n-2) for two steps, and the total numbers is the number of ways to use one of these options - thus the summation).

If you look carefully - this is also a well known series - the fibonacci numbers, and the solution is simply calculating each number buttom-up instead of re-calculating the recursion over and over again, resulting in much more efficient solution.

Upvotes: 15

Related Questions