[LeetCode 70] Climbing Stairs

Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps

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

1 <= n <= 45

function climbStairs(n: number): number {
    // how many ways to climb to step
    const stepToCount: Map<number, number> = new Map<number, number>();
    
    const climb = (step: number): number => {
        if(step === 0 || step === 1) return 1;
        if(stepToCount.has(step)) return stepToCount.get(step)
        
        const step1: number = climb(step - 1)
        const step2: number = climb(step - 2)
        if(!stepToCount.has(step - 1)) stepToCount.set(step - 1, step1)
        if(!stepToCount.has(step - 2)) stepToCount.set(step - 2, step2)
        
        return step1 + step2
    }
    
    return climb(n)
};

function climbStairs(n: number): number {
    // store number of ways to climb nth stair
    let table: number[] = Array(n + 1).fill(0);
    // there is only 1 way to climb 0 or 1 stairs
    table[0] = 1;
    table[1] = 1;
    
    for(let i = 2; i <= n; i++) {
	// the way to climb ith stair comes from the sum of i - 1 and i - 2 ways
        table[i] = table[i - 1] + table[i - 2];
    }
    return table[n]
};