Staircase

This one is a classic: Given a staircase with n steps and a list of possible hops, find the number of ways you can get to the top

Algorithm

      _ 
    _|
  _|
_|

If our hops are [1, 2] then for the 3 step staircase above we can
reach the top via [1, 1, 1], [1, 2], [2, 1] so 3 ways. If there was
a 4th step we can do [1, 1, 1, 1], [1, 1, 2], [1, 2, 1], [2, 1, 1], [2, 2]
i.e. 5 ways. Noticing a pattern?:

1 step	2 steps	3 steps	4 steps	5 steps	6 steps
1	1 way for 1 step + 1 way via [2]= 2	2 ways for 2 step + 1 way for 1 ways for 1 step = 3	3 ways for 3 step + 2 ways for 2 step = 5	8	13

Since we have 2 hops: [1, 2], we get the fibonacci sequence. If we added a 3 to our possible hops: [1, 2, 3] we'd add the # of ways from the current step - 1, current step - 2, and current step - 3, so we'd have:

1 step	2 steps	3 steps	4 steps	5 steps
1	1 way for 1 step + 1 way via [2] = 2	1 way for 1 step + 2 ways for 2 step + 1 way via [3]= 4	1 way for 1 step + 2 ways for 2 step + 4 ways for 3 steps: = 7	13

Implementation

def numWaysUpStairs(n: Int, hops: List[Int]): Int =
  1.until(n + 1)
    .foldLeft(Vector.fill(n + 1)(0).updated(0, 1)) { (out, i) =>
      hops.foldLeft(out) { (out, incr) =>
        if (incr <= i)
          out.updated(i, out(i) + out(i - incr))
        else out
      }
    }(n)