obdelnik-12.py

#!/usr/bin/python3
# Počet dláždění obdélníka 1×n kostkami 1×1 a 1×2

# Rekurzivní funkce s exponenciální složitostí
def d(n):
    if n <= 1:
        return 1
    return d(n-1) + d(n-2)

# Všimli jsme si, že d() počítá spoustu podproblémů opakovaně,
# tak jsme dodělali kešování známých mezivýsledků. Tím se časová
# složitost zlepšila na O(n), ale chvíli trvá to dokázat.
pamet = { 0: 1, 1: 1 }
def d2(n):
    if n not in pamet:
        pamet[n] = d2(n-1) + d2(n-2)
    return pamet[n]

# Tady počítáme tytéž podproblémy od nejmenšího k největšímu.
# Rekurzi jsme nahradili obyčejným cyklem, složitost je evidentně O(n).
def d3(n):
    D = [1, 1] + [0]*n
    for i in range(2, n+1):
        D[i] = D[i-1] + D[i-2]
    return D[n]

# Konečně jsme si všímli, že není potřeba pamatovat si všechny
# mezivýsledky, ale stačí předchozí dva. Tím jsme snížili prostorovou
# složitost na konstantní.
def d4(n):
    a = b = 1
    for i in range(2, n+1):
        a, b = a+b, a
    return a