Climbing Stairs

climbing_stairs.rs

use std::collections::HashMap;

impl Solution {
    pub fn fib(n: i32, cache: &mut HashMap<i32, i32>) -> i32 {
        if n <= 2 { return n; }
        else if !cache.contains_key(&(n-1)) && !cache.contains_key(&(n-2)) {
            let a = Self::fib(n - 1, cache);
            let b = Self::fib(n - 2, cache);

            cache.insert(n - 1, a);
            cache.insert(n - 2, b);
        }

        return *cache.get(&(n - 1)).unwrap() + *cache.get(&(n - 2)).unwrap();
    }
    
    pub fn climb_stairs(n: i32) -> i32 {
        Self::fib(n, &mut HashMap::new())
    }
}

https://leetcode.com/problems/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?