Approach #1: Dynamic Programming [Accepted]
Intuition
There is a clear recursion available: the final cost f[i]
to climb the staircase from some step i
is f[i] = cost[i] + min(f[i+1], f[i+2])
. This motivates dynamic programming.
Algorithm
Let's evaluate f
backwards in order. That way, when we are deciding what f[i]
will be, we've already figured out f[i+1]
and f[i+2]
.
We can do even better than that. At the i
th step, let f1, f2
be the old value of f[i+1]
, f[i+2]
, and update them to be the new values f[i], f[i+1]
. We keep these updated as we iterate through i
backwards. At the end, we want min(f1, f2)
.
Complexity Analysis

Time Complexity: where is the length of
cost
. 
Space Complexity: , the space used by
f1, f2
.
Analysis written by: @awice.