I cannot understand the DP solution of javascript in leetcode 70

Question

I am confused by the reference answer of climbing stairs in leetcode.

Here is the problem:

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?

   var climbStairs = function(n) {

    if (n < 1) return 0;
    if (n == 1) return 1;
    if (n == 2) return 2;

    // a saves the second-to-last sub-state data, b saves the first sub-state data, temp saves the current state data
    let a = 1, b = 2;
    let temp = a + b;
    for (let i = 3; i <= n; i++) {
        temp = a + b;
        a = b;
        b = temp; 
    }
    return temp; 
   };

The answer uses DP to solve, but I cannot understand how the for loop works，I think I missed some javascript characteristics.

What’s unclear about the actual loop? It’s a regular loop from 3 to n inclusive. Or do you mean the algorithm it uses to solve this? — Sami Kuhmonen
– Sami Kuhmonen, Commented Jun 1, 2019 at 19:34
@SamiKuhmonen I cannot read "a = b; b = temp" in the loop, and why the return value temp is the final answer? — host J
– host J, Commented Jun 1, 2019 at 19:46

GaloisGirl · Accepted Answer · 2019-06-01 21:02:24Z

1

This is equivalent to the coin change problem:

Given a set of coins and amount, Write an algorithm to find out how many ways we can make the change of the amount using the coins given.

N is your amount, and the available coins are 1 and 2 cents.

Here's a comprehensive explanation of the coin change problem: https://hackernoon.com/the-coin-change-problem-explained-ddd035a8f22f

Here's a thread on Quora: https://www.quora.com/What-is-an-easy-way-to-understand-the-coin-change-problem-in-dynamic-programming

answered Jun 1, 2019 at 21:02

GaloisGirl

1,5161 gold badge8 silver badges15 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

I cannot understand the DP solution of javascript in leetcode 70

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related