Programu ya nguvu (kumbukumbu dhidi ya ndani ya meza) ni nini?

Question

Accepted Answer

**Programu ya nguvu (DP)** inayotatua matatizo na **matatizo yanayoingiliana** na **muundo mzuri wa chini** kwa kuhesabu kila tatizo kimoja mara moja na kutumia tena matokeo. Mitindo miwili ni **kumbukumbu** (kutoka juu chini) na **ndani ya meza** (kutoka chini juu).

## Wazo

Rekursio nyingi inahesabu tena matatizo sawa kwa njia ya kielelezo. DP inahifadhi yazo, na kulipuka kazi ya kielelezo kuwa kielelezo cha polinomia.

## Kumbukumbu (kutoka juu chini)

```python
from functools import lru_cache

@lru_cache(maxsize=None)               # cache results automatically
def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)     # each n computed once
```

## Ndani ya meza (kutoka chini juu)

```python
def fib_table(n):
    if n < 2:
        return n
    dp = [0, 1]
    for i in range(2, n + 1):
        dp.append(dp[i - 1] + dp[i - 2])  # build up from base cases
    return dp[n]
```

## Kumbukumbu dhidi ya ndani ya meza

| | Kumbukumbu | Ndani ya meza |
|---|------------|------------||
| Mwelekeo | top-down recursion | bottom-up iteration |
| Huhesabu | majimbo yaliyohitajika tu | majimbo yote |
| Hatari | kuzamia stack | hakuna |
| Nafasi | inaweza kupunguzwa | mara nyingi inaweza kupunguzwa hadi O(1) safu |

## Matatizo

Fibonacci: kutoka O(2ⁿ) nyingi hadi **O(n)** wakati, O(n) (au O(1)) nafasi.

## Wakati wa kutumia / mitego

Tumia DP wakati matatizo **yanaingiliana**. Fafanua hali na muundo unaourudia kwa makini — hiyo ndio sehemu ngumu. Ikiwa matatizo hayaingiliani, mgawanyiko-na-shutrani rahisi inatosha.

## Kwa nini ni muhimu

DP inabadilisha matatizo ya kielelezo yasiyoweza kutatuliwa — njia fupi zaidi, umbali wa hariri, begi — kuwa yenye ufanisi.

Skili ya kutambua hali na muundo unaourudia ni miongoni mwa yenye thamani zaidi katika mahojiano ya algorithms.

Ini ndio msingi wa mifumo halisi kutoka kwa zana za diff hadi mlinganisho wa mfuatano wa bioinformatics.