Dynamic Programming

code: python

# O(n), O(n)

def f(n: int) -> int:

if n <= 1:

return n

for i in range(2, n + 1):

def test_f():

assert f(0) == 0

assert f(1) == 1

assert f(2) == 1

assert f(3) == 2

assert f(4) == 3

assert f(5) == 5

assert f(10) == 55