Explanation of the problem


  • 0
    F

    I have read some the top viewed solutions, they are brilliant. I am not trying to improve the solution of this question, but try to explain the solution in an easier manner.

    Recap: you have 2 options, you can take 1 step, or 2 steps at once to climb N steps stair. How many distinct ways can you climb to the top?

    If stair only has 1 step (N=1), we have 1 way to climb.
    If stair is 2 steps (N=2), we have 2 ways to climb. Either take 1 step and then 1 step, or take 2 steps at once.
    If stair is 3 steps (N=3), if the first step we take 1, we have 2 steps remain, and we have 2 ways to complete the remaining 2 steps(N=2 case); if the first step we take 2, we have 1 way to complete the remaining 1 step (N=1 case).

    As you see, the fibonacci pattern is obvious.

    N= number of steps
    S1 first step take 1 step
    S2 first step take 2 steps

    N    S1    S2Total ways = S1 + S2
    11N/A  1
    2112
    3213
    4325
    5538
    68513

    Let' say, the stair is 5 steps. If the first step takes 1 step, 4 steps remain. As the table show, we have 5 ways to complete a 4 steps stair. If the first step takes 2 steps, 3 steps remain, and we have 3 ways to complete them. So, in total, we have 8 ways (5+3) to climb a 5 steps stair.

    Thus, total ways is a fibonacci number (starts from N=3)

    Now, what if you can take 1 step, 2 steps, or 3 steps at once. How many distinct ways can you climb to the top?

    // in Java
    static long climbStair(int n){
    	//	we have 3 options, take 1,2,3 steps,
    	if (n <= 0) return 0;
    	if (n <= 1) return 1;
    	if (n <= 2) return 2;
    	if (n <= 3) return 4;
    
    
    	long[] solutions = new long[n+1];
    	// n indicates number of stairs.
    	// value is the number of distinct ways to climb the stair.
    	solutions[0]=0;
    	solutions[1]=1;
    	solutions[2]=2;
    	solutions[3]=4;
    
    	for (int i = 4; i < n+1; i++)
    		solutions[i] = solutions[i-1] + solutions[i-2] + solutions[i-3];
    
    	return solutions[n];
    }
    

    Note: my post and code are solely to explain the question.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.