leetcode day 16: climbing steps

You have an N step staircase that you can climb either 1 or 2 steps at a time. How many ways are there to climb it?

It was clear that this was a recurrence relation, and my instinct was to cache the computed values. This would be a better attack for a more complex problem; this is just a Fibonacci sequence!

I did do the cached one first, and I am very proud of myself for properly passing the cache through:

func climbStairs(n int) int {
    // this smells of caching...and a Fibonacci recurrence.
    // we know that if we're at N, it takes 0 steps to finish.
    // if we're at n - 1, there is one option: take 1 step.
    // if we're at n - 2, there are two options, 2 1 step, or 1 2 step.
    cache := map[int]int{
        0: 0,
        1: 1,
        2: 2,
    }
    return assist(n, &cache)
}

func assist(n int, cache *map[int]int) int {
    if steps, ok := (*cache)[n]; ok {
        return steps
    }
    (*cache)[n] = assist(n-1, cache) + assist(n-2, cache)
    return (*cache)[n]
}

A huge winner on runtime: 100%! But poor on memory: bottom 9%. An iterative Fibonacci calculation’s probably going to win on this one…Interestingly, it doesn’t! Runtime 82%, memory 33%.

func climbStairs(n int) int {
    // this smells of caching...and a Fibonacci recurrence.
    backTwo := 1
    backOne := 2
    sum := 0
    if n == 1 {
        return 1
    }
    if n == 2 { 
        return 2
    }
    for current := n; current > 2; current-- {
        sum = backOne + backTwo
        backTwo = backOne
        backOne = sum
    }
    return sum
}

Off to the solutions to see what’s there.. the most compact iterative solution still isn’t any better on memory, but is the same speed as the cached one I wrote:

func climbStairs(n int) int {
    next, secondNext := 0, 1
    for ; n > 0; n-- {
        next, secondNext = secondNext, next + secondNext
    }
    return secondNext
}

I’ll call this a win, and ++ for dynamic programming.