Approach #1: Dynamic Programming [Accepted]
There is a clear recursion available: the final cost
f[i] to climb the staircase from some step
f[i] = cost[i] + min(f[i+1], f[i+2]). This motivates dynamic programming.
f backwards in order. That way, when we are deciding what
f[i] will be, we've already figured out
We can do even better than that. At the
i-th step, let
f1, f2 be the old value of
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
Time Complexity: where is the length of
Space Complexity: , the space used by
Analysis written by: @awice.