The staircase-climbing code

Let's translate the table-filling seen above into Python code. We create a table dp of size n+1, set the two base values, then fill each cell with a simple loop, without any recursion or redundant calls.

def escalier(n):
    if n == 0:
        return 1
    dp = [0] * (n + 1)
    dp[0] = 1
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

This bottom-up version has a time complexity of O(n): a single loop that fills n+1 cells, each in constant time. This is the same order of magnitude as the memoized version, but without the risk of a call stack overflow that can occur with too-deep a recursion, and without the hidden cost of recursive function calls.

You can even reduce the memory used: since dp[i] only depends on the two previous cells, there is no need to keep the whole table, only the last two values:

def escalier_optimise(n):
    if n == 0:
        return 1
    precedent, courant = 1, 1   (dp[0], dp[1])
    for i in range(2, n + 1):
        precedent, courant = courant, precedent + courant
    return courant

This same method applies to other classic problems such as coin change (counting the minimal number of coins to reach a sum): a table dp is built where dp[s] represents the minimal cost for sum s, deduced from the values dp[s - piece] already computed for each available coin. The principle remains identical: identify the recurrence between subproblems, then fill a table from the smallest case to the largest, never recomputing a cell already set.