Ludium - Learn by Doing

Fill a Fibonacci Table from the Bottom Up

Write the function fibTable(n) that returns a list of length n + 1 whose entry at index i is the Fibonacci number $\text{fib}(i)$ , using the lecture's convention $\text{fib}(0) = \text{fib}(1) = 1$ .

Assume n is a non-negative int. Memoization fills a table on the way down a recursion; here fill it on the way up: start from the base cases and compute each new entry from entries already in the list. Do not use recursion: fibTable must work for n as large as 3000, far deeper than Python's recursion limit.

print(fibTable(6))          # [1, 1, 2, 3, 5, 8, 13]
print(fibTable(0))          # [1]
print(fibTable(120)[-1])    # 8670007398507948658051921

def fibTable(n):
    """n: an int >= 0.
    Return the list [fib(0), fib(1), ..., fib(n)], where fib(0) = fib(1) = 1,
    built without recursion."""
    pass

def fibTable(n):
    """n: an int >= 0.
    Return the list [fib(0), fib(1), ..., fib(n)], where fib(0) = fib(1) = 1,
    built without recursion."""
    pass

Scratchpad— run any Python to test ideas

# Scratchpad — run any Python here to test ideas.
# Anything you write below stays separate from the problem's tests.

print("hello, world")

# Scratchpad — run any Python here to test ideas.
# Anything you write below stays separate from the problem's tests.

print("hello, world")

Python runtime ready in a moment

Visible tests · 2Examples — click to expand

fibTable(6)

fibTable(1)

Hidden tests · 3Bodies hidden — pass/fail only

Hidden test 1

Hidden test 2

Hidden test 3

Fill a Fibonacci Table from the Bottom Up

print(fibTable(6))          # [1, 1, 2, 3, 5, 8, 13]
print(fibTable(0))          # [1]
print(fibTable(120)[-1])    # 8670007398507948658051921

def fibTable(n):
    """n: an int >= 0.
    Return the list [fib(0), fib(1), ..., fib(n)], where fib(0) = fib(1) = 1,
    built without recursion."""
    pass

def fibTable(n):
    """n: an int >= 0.
    Return the list [fib(0), fib(1), ..., fib(n)], where fib(0) = fib(1) = 1,
    built without recursion."""
    pass

Scratchpad— run any Python to test ideas

# Scratchpad — run any Python here to test ideas.
# Anything you write below stays separate from the problem's tests.

print("hello, world")

# Scratchpad — run any Python here to test ideas.
# Anything you write below stays separate from the problem's tests.

print("hello, world")

Python runtime ready in a moment

Visible tests · 2Examples — click to expand

fibTable(6)

fibTable(1)

Hidden tests · 3Bodies hidden — pass/fail only

Hidden test 1

Hidden test 2

Hidden test 3

Coding challenges on brute force and dynamic programming

Fill a Fibonacci Table from the Bottom Up

Coding challenges on brute force and dynamic programming

Fill a Fibonacci Table from the Bottom Up