Dinamik dasturlash

from functools import lru_cache


# 1-usul: memoizatsiya (yuqoridan pastga)
@lru_cache(maxsize=None)
def fib_memo(n):
    if n < 2:
        return n
    return fib_memo(n - 1) + fib_memo(n - 2)


# 2-usul: tabulyatsiya (pastdan yuqoriga)
def fib_jadval(n):
    if n < 2:
        return n

    jadval = [0] * (n + 1)
    jadval[1] = 1

    for i in range(2, n + 1):
        jadval[i] = jadval[i - 1] + jadval[i - 2]

    return jadval[n]


# 3-usul: xotirani optimallashtirish - butun jadval kerak emas
def fib_optimal(n):
    if n < 2:
        return n

    oldingi, joriy = 0, 1
    for _ in range(2, n + 1):
        oldingi, joriy = joriy, oldingi + joriy
    return joriy


for funksiya in [fib_memo, fib_jadval, fib_optimal]:
    print(f"{funksiya.__name__:<14}{funksiya(50):>15,}")

def zinapoya(n):
    """n ta pog'onaga chiqish usullari soni."""
    if n <= 2:
        return n

    ikki_oldin, bir_oldin = 1, 2
    for _ in range(3, n + 1):
        joriy = ikki_oldin + bir_oldin
        ikki_oldin, bir_oldin = bir_oldin, joriy

    return bir_oldin


for pogonalar in range(1, 9):
    print(f"{pogonalar} ta pog'ona -> {zinapoya(pogonalar):>3} xil usul")

def eng_kam_tanga(tangalar, summa):
    """Minimal tangalar soni. O(summa * len(tangalar))."""
    CHEKSIZ = float("inf")
    jadval = [0] + [CHEKSIZ] * summa

    for joriy in range(1, summa + 1):
        for tanga in tangalar:
            if tanga <= joriy and jadval[joriy - tanga] + 1 < jadval[joriy]:
                jadval[joriy] = jadval[joriy - tanga] + 1

    return jadval[summa] if jadval[summa] != CHEKSIZ else -1


def tangalarni_korsat(tangalar, summa):
    """Qaysi tangalar ishlatilganini ham qaytaradi."""
    CHEKSIZ = float("inf")
    jadval = [0] + [CHEKSIZ] * summa
    tanlov = [None] * (summa + 1)

    for joriy in range(1, summa + 1):
        for tanga in tangalar:
            if tanga <= joriy and jadval[joriy - tanga] + 1 < jadval[joriy]:
                jadval[joriy] = jadval[joriy - tanga] + 1
                tanlov[joriy] = tanga

    if jadval[summa] == CHEKSIZ:
        return None

    natija = []
    qolgan = summa
    while qolgan > 0:
        natija.append(tanlov[qolgan])
        qolgan -= tanlov[qolgan]

    return sorted(natija, reverse=True)


tangalar = [1, 5, 10, 25]
for summa in [11, 30, 63]:
    soni = eng_kam_tanga(tangalar, summa)
    tanlangan = tangalarni_korsat(tangalar, summa)
    print(f"{summa:>3} so'm -> {soni} ta tanga: {tanlangan}")

def ryukzak(buyumlar, quvvat):
    """0/1 ryukzak masalasi. O(n * W)."""
    n = len(buyumlar)
    jadval = [[0] * (quvvat + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        nomi, ogirlik, qiymat = buyumlar[i - 1]

        for w in range(quvvat + 1):
            if ogirlik > w:
                jadval[i][w] = jadval[i - 1][w]            # sig'maydi
            else:
                olmaslik = jadval[i - 1][w]
                olish = jadval[i - 1][w - ogirlik] + qiymat
                jadval[i][w] = max(olmaslik, olish)

    # Qaysi buyumlar tanlanganini tiklaymiz
    tanlangan = []
    w = quvvat
    for i in range(n, 0, -1):
        if jadval[i][w] != jadval[i - 1][w]:
            nomi, ogirlik, qiymat = buyumlar[i - 1]
            tanlangan.append(buyumlar[i - 1])
            w -= ogirlik

    return jadval[n][quvvat], tanlangan[::-1]


buyumlar = [
    ("Noutbuk",     3, 2000),
    ("Fotoapparat", 2, 1200),
    ("Kitob",       1,  300),
    ("Planshet",    2,  900),
    ("Naushnik",    1,  500),
]
QUVVAT = 5

qiymat, tanlangan = ryukzak(buyumlar, QUVVAT)

print(f"Ryukzak quvvati: {QUVVAT} kg\n")
print(f"{'Buyum':<16}{'Og‘irlik':>10}{'Qiymat':>10}")
print("-" * 36)
for nomi, ogirlik, narx in tanlangan:
    print(f"{nomi:<16}{ogirlik:>9} kg{narx:>10,}")
print("-" * 36)
print(f"{'JAMI':<16}{sum(b[1] for b in tanlangan):>9} kg{qiymat:>10,}")

def ryukzak_jadvalini_korsat(buyumlar, quvvat):
    n = len(buyumlar)
    jadval = [[0] * (quvvat + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        _, ogirlik, qiymat = buyumlar[i - 1]
        for w in range(quvvat + 1):
            if ogirlik > w:
                jadval[i][w] = jadval[i - 1][w]
            else:
                jadval[i][w] = max(jadval[i - 1][w],
                                   jadval[i - 1][w - ogirlik] + qiymat)

    print("       " + "".join(f"{w:>7}" for w in range(quvvat + 1)))
    print("       " + "  kg".rjust(7 * (quvvat + 1)))
    for i, qator in enumerate(jadval):
        nomi = "bo'sh" if i == 0 else buyumlar[i - 1][0][:6]
        print(f"{nomi:<7}" + "".join(f"{q:>7,}" for q in qator))


ryukzak_jadvalini_korsat(buyumlar, 5)

def eng_uzun_umumiy(birinchi, ikkinchi):
    """Eng uzun umumiy qism ketma-ketlikni topadi. O(n * m)."""
    n, m = len(birinchi), len(ikkinchi)
    jadval = [[0] * (m + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if birinchi[i - 1] == ikkinchi[j - 1]:
                jadval[i][j] = jadval[i - 1][j - 1] + 1
            else:
                jadval[i][j] = max(jadval[i - 1][j], jadval[i][j - 1])

    # Ketma-ketlikni tiklaymiz
    natija = []
    i, j = n, m
    while i > 0 and j > 0:
        if birinchi[i - 1] == ikkinchi[j - 1]:
            natija.append(birinchi[i - 1])
            i -= 1
            j -= 1
        elif jadval[i - 1][j] >= jadval[i][j - 1]:
            i -= 1
        else:
            j -= 1

    return "".join(reversed(natija))


print(eng_uzun_umumiy("dasturlash", "dasturchi"))
print(eng_uzun_umumiy("ALGORITM", "ALGEBRA"))

def tahrirlash_masofasi(birinchi, ikkinchi):
    """Levenshtein masofasi: qo'shish, o'chirish, almashtirish. O(n * m)."""
    n, m = len(birinchi), len(ikkinchi)
    jadval = [[0] * (m + 1) for _ in range(n + 1)]

    for i in range(n + 1):
        jadval[i][0] = i                    # hammasini o'chirish
    for j in range(m + 1):
        jadval[0][j] = j                    # hammasini qo'shish

    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if birinchi[i - 1] == ikkinchi[j - 1]:
                jadval[i][j] = jadval[i - 1][j - 1]
            else:
                jadval[i][j] = 1 + min(
                    jadval[i - 1][j],        # o'chirish
                    jadval[i][j - 1],        # qo'shish
                    jadval[i - 1][j - 1],    # almashtirish
                )

    return jadval[n][m]


juftliklar = [("kitob", "kitobcha"), ("dastur", "dasturchi"), ("salom", "salam")]
for a, b in juftliklar:
    print(f"{a:<10} -> {b:<12} {tahrirlash_masofasi(a, b)} ta amal")