[Leetcode] Climbing Stairs

70. Climbing Stairs

You are climbing a staircase. It takes nsteps to reach the top.

Each time you can either climb 1or 2steps. 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

Constraints:

1 <= n <= 45

how to approach?

Brute Force

function climbStairs(n: number): number {

    function climbSteps(i: number, n: number): number {
        if (i > n) {
            return 0;
        }
        if (i == n) {
            return 1;
        }
        return climbSteps(i + 1, n) + climbSteps(i + 2, n);
    }

    return climbSteps(0, n)
};

1. create the function to return the 1step + 2 step values.
2. at the end the solution return the function starting from 0 end at n.
3. this means this function will check all the possible path using 1step + 2step until n stairs.
4. in the function, it will check the where the current step(i) is and what is the goal(n), if it doesn't meet i>n or i==n condition then it will return the 1 step + 2 steps.

summary

this will check all the possible path using 1step + 2step. if current step after the calculation then that is not valid path, if the current step meets n stairs then that means it's valid path with the 1step + 2 steps variation.

Recursion with Memoization

function climbStairs(n: number): number {
    let memo: number[] = new Array(n + 1).fill(0);

    function climb_Stairs(i: number, n: number, memo: number[]): number {
        if (i > n) {
            return 0;
        }
        if (i == n) {
            return 1;
        }
        if (memo[i] > 0) {
            return memo[i];
        }
        memo[i] = climb_Stairs(i + 1, n, memo) + climb_Stairs(i + 2, n, memo);
        return memo[i];
    }

    return climb_Stairs(0, n, memo);
}

1. first create memo array which has 0 to n element as 0
2. create function to get i step, n stairs, and the memo array.
3. lastly, return the function gets 0, n, and memo to return the distinct ways from 0 to n stairs by 1 step or 2 steps.
4. in the function, set base cases, if steps are bigger than stairs then it's nono, if steps are same as stairs then it's valid path, return 1.
5. the memoization will happen as it call the function recursively checking 1 step or 2 steps. so i will be incremented by one or two which represent the from i location it will go further 1 step or 2 steps. and it also will be calculated and saved as memo[i].
6. memo[i] will be returned at last, before that, if there is already calculated result which means memo[i] is bigger than 0 then it will be returned early in if block so function can use it not calculate it again.

summary

to save the calculated result in memo, call the function for memo[i] element recursively. and lastly return the distinct ways by call the function with 0, n, and memo array.

Dynamic Programming

function climbStairs(n: number): number {
    if (n == 1) {
        return 1;
    }
    let dp: number[] = new Array(n + 1).fill(0);
    dp[1] = 1;
    dp[2] = 2;
    for (let i = 3; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

1. when stair is only one, only 1 step is valid. so return 1.
2. create dp array has length of n+1 and fill with 0.
3. dp's first element and second element will be 1 and 2. because 1 stair only have one 1 case and 2 stairs has 2 cases(1+1, 2)
4. create for loop starting from index 3, and the dp's i th index element will be the sum of dp's i-1 and dp's i-2 element.
5. lastly return the last element in dp array.

summary

Use the base case when only 1 or 2 step is available in stairs. think of the paths to be there at i th stairs. it's only valid when there was the ways to be on i-1 th stair or i-2 th stair.

Fibonacci Number

function climbStairs(n: number): number {
    if (n == 1) {
        return 1;
    }
    let first = 1;
    let second = 2;
    for (let i = 3; i <= n; i++) {
        let third = first + second;
        first = second;
        second = third;
    }
    return second;
}

1. when input n equals to 1, then return 1.
2. and set first and second valid paths for 1 stair and 2 stairs.
3. for loop will start at index 3, and set third as sum of first and second.
4. first will be second and second will be third.
5. at the end, return second value since that will be last value in the Fibonacci number.

summary

think of this as fibonacci number and use the base cases.