Dynamic Programming. Climbing Stairs.

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?

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

What is subproblem here?

- At each step we can take either 1 or 2 steps

- So, we can break it down into subproblems of taking 1 step and 2 steps

• At 0, we have only 1 way to reach 0 i.e 0 itself, totalWays[0] = 1
• At 1, we have only 1 way to reach 1 i.e from 0, totalWays[1] = 1
• At 2, we have 2 ways to reach 2 i.e either from 0 or 1, totalWays[2] = totalWays[0] + totalWays[1] = 2
• At 3, we have 2 ways to reach 3 i.e either from 1 or 2, totalWays[3] = totalWays[1] + totalWays[2] = 3

But notice, at 2 we have 2 ways to reach 2, so we can add that to 3

and get 3 ways to reach 3

function climbStairs(n){
  dp = new Array(n + 1)
    dp[0] = 1
    dp[1] = 1
    for i from 2 to n:
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]
}

To recognise characteristics for using dynamic programming to solve a problem:

1. Overlapping Subproblems:

Notice that the number of distinct ways to reach the current step depends on the number of distinct ways to reach the previous steps.

For example, to reach step i, you can either come from step i-1 by taking a single step or come from step i-2 by taking two steps.

2. Optimal Substructure:

The optimal solution for reaching the i-th step can be constructed from

the optimal solutions of the previous steps.

n+1 because we need to account for the 0th step as well.

Since the steps are numbered from 1 to n, we need an array of size n+1 to store the number of distinct ways to reach each step.

This is a Dynamic programming problem. Which means we can look for

• Recurrence Relation:

Basically a repeated sub problems if solved can solve the main problem as a whole.

For example, if we know how many steps it can take to get to

1. last step i.e previous from the finish line
2. 2nd last step i.e previous from the previous of the finish line

<__top__>

|

--------<last step i.e prev from top> A

|

-------<2nd last step i.e prev from A> B

|

At this point if we know how many ways there are to get to A and B, then we can easily calculate it form top i.e to finish climbing the stairs.

Similarly, To get to A,

if we knew how many ways to get to Prev of A + prev of Previous of A, we can calculate , how many ways there are to get to A.

In a way we can see our recurrence relations as:

Ways to get to A = number of ways @ [A - 1] + number of ways @[A -2]

So using this formula we can easily calculate. Number of minimum ways to get to the top

Now let's see how we can solve this problem:

0 1 2 3 4

cost = [20 15 30 5]

minCost to reach @ 4 = minCost of(2, 3)

minCost(n)

/ \

minCost(n-1) minCost(n-2)

do we want both of them? we want the min between these two values

what is minCost(index = 2)?

minCost(n)

/ \

Min(minCost(n-1) minCost(n-2)) + cost(n)

/ \

Min(minCost(n-2), minCost(n-3)) + cost(n - 1) (minCost(n-3), minCost(n-4)) + cost(n-2)

Note that,

minCost of reaching these steps includes the cost of the step itself.

recurrence relation Math.min(minCost(n-1), minCost(n - 2)) + cost(n)

function climbStairs2(n) {
  if (n === 1 || n === 2) return n;
  let dp = new Array(n + 1);
  dp[0] = 1;
  dp[1] = 1;
  dp[2] = dp[0] + dp[1];
  dp[3] = dp[1] + dp[2];

  for (let i = 4; i <= n; i++) {
    dp[i] = dp[i - 2] + dp[i - 1];
  }
  return dp[n];
}

if we observe this, we can optimize this further down where we don't need any array to store any value:

function optimizeClimb(n){
    if(n === 1 || n ===2 ) return n
    let prev = 1
    let prevPrev = 2

    for(let i = 3; i <=n; i++){
        let temp = prev + prevPrev
        prev = prevPrev
        prevPrev = temp
    }

    return prevPrev 
}

Time Complexity = O(N)

Space Complexity = O(1)

When submitted to leet code this is the result: