def fibonacci_tabulation(n):
    """DP implementation of fibonacci. O(n) runtime, O(n) space"""
    d = [0] * (n + 1)
    d[1] = 1
    d[2] = 1
    for i in range(3, n + 1):
        d[i] = d[i - 1] + d[i - 2]
    return d[n]