18.01.2024
70. Climbing Stairs easy
blog post
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/476
Problem TLDR
Ways to climb n stairs by 1 or 2 steps.
Intuition
Start with brute force DFS search: either go one or two steps and cache the result in a HashMap<Int, Int>. Then convert solution to iterative version, as only two previous values matter.
Approach
no need to check
if n < 4
save some lines of code with
also
Complexity
Time complexity:
O(n)Space complexity:
O(1)
Code
fun climbStairs(n: Int): Int {
var p = 0
var c = 1
for (i in 1..n) c += p.also { p = c }
return c
}
Bonus: Rust
pub fn climb_stairs(n: i32) -> i32 {
(0..n).fold((0, 1), |(p, c), _| (c, p + c)).1
}