Объясните мне динамическое программирование

Динамическое программирование - НЕ рекурсия, а способ решить задачу БЕЗ рекурсии. Двигаясь в цикле от начала к нужному значению и на каждом следующем шаге используя результаты, полученные на предыдущем шаге.

Например, числа Фибоначчи. Рекурсией они вычисляются так:

 def fib(n):
  if n < 2: return n
  return fib(n - 1) + fib(n - 2)

print(fib(int(input()))) 

Мы движемся от конца к началу, на каждом шаге вычисляя два предшествующих числа.

А динамическим программированием так:

 n = int(input())
fib = [0, 1]
for _ in range(n - 1): fib.append(fib[-1] + fib[-2])
print(fib[n]) 

Мы движемся от начала к концу, на каждом шаге добавляя новое число, полученное из уже вычисленных.

P.S. Вот, кстати, задача для динамического программирования: https://otvet.mail.ru/question/238124198