Cad is ionchur ríomhchlárúchán dinimic (meabhrúchán i gcoinne tábhla)?

Question

IT Interview Practice · Accepted Answer

**Réitíonn ionchur ríomhchlárúchán dinimic (DP)** fadhbanna le **fho-fhadhbanna atá i bhfoluain** agus **dromchla fhóthanach** trí gach fo-fhadhb a ríomh aon uair amháin agus an toradh a athúsáid. Is iad an dá stíl **meabhrúchán** (top-down) agus **tábhla** (bottom-up).

## An smaoineamh

Athríomhann athchúrsáil dhíchallach na fo-fhadhbanna céanna go heaspónantúil. Cuireann DP i taisce iad, ag laghdú na hoibre easpónantúil go polynómach.

## Meabhrúchán (top-down)

```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
```

## Tábhla (bottom-up)

```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]
```

## Meabhrúchán i gcoinne tábhla

| | Meabhrúchán | Tábhla |
|---|------------|--------|
| Treo | athchúrsáil top-down | atriall bottom-up |
| Ríomhann | stáit riachtanacha amháin | gach stát |
| Baol | foluain staic | faic |
| Spás | is féidir a ghearradh síos | go minic intuigthe go O(1) sraitheanna |

## Castacht

Fibonacci: ó O(2ⁿ) díchallach go **O(n)** am, O(n) (nó O(1)) spás.

## Cathain a úsáid / pithreanna

Úsáid DP nuair a **fhorluíonn** fo-fhadhbanna. Sainmhíníonn an stát agus an atarlú go cúramach — sin an chuid dhian. Mura bhforluíonn fo-fhadhbanna, is leor roinnt-agus-conquer simplí.

## Cén fáth a bhíonn sé tábhachtach

Macláonn DP fadhbanna easpónantúla dosocraithe — cosáin is giorra, fad in-eagar, mála — ina gcinn éifeachtacha.

Is iad an scil a shainaithint stáit agus atarlú ina measc an fhéadfaidh in iontrálacha algartam.

Tá sé fúithi ag córais fhíor ó ghréine-uirlisí go ailíniú seichimh bhitheolaíochta.

	Meabhrúchán	Tábhla
Treo	athchúrsáil top-down	atriall bottom-up
Ríomhann	stáit riachtanacha amháin	gach stát
Baol	foluain staic	faic
Spás	is féidir a ghearradh síos	go minic intuigthe go O(1) sraitheanna

An smaoineamh

Meabhrúchán (top-down)

Tábhla (bottom-up)

Meabhrúchán i gcoinne tábhla

Castacht

Cathain a úsáid / pithreanna

Cén fáth a bhíonn sé tábhachtach

Ceisteanna gaolmhara