ஒரே தருணத்தில் நினைவகம் (memoization) மற்றும் அட்டவணைமை (tabulation) என்ற இயங்கு நிரல்படுத்தல் (dynamic programming) என்றால் என்ன?

Question

Accepted Answer

**இயங்கு நிரல்படுத்தல் (DP)** என்பது **மீண்டும் மீண்டும் உள்ள துணைச் சிக்கல்கள்** மற்றும் **சரியான உபCoach்ச அமைப்பு** உள்ள சிக்கல்களைத் தீர்க்கிறது, ஒவ்வொரு துணைச் சிக்கலையும் ஒரு முறை கணக்கிட்டு, முடிவை மீண்டும் பயன்படுத்துவதன் மூலம். இரு நடைமுறைகளும் **நினைவகம்** (மேல்-கீழ்) மற்றும் **அட்டவணைமை** (கீழ்-மேல்) ஆகும்.

## கருத்து

பாவனையற்ற சுழல் விதி ஒரே துணைச் சிக்கல்களை அளவுக்கதிகமாக மீண்டும் கணக்கிடுகிறது. DP அவற்றைக் குறிப்பாகக் கொள்கிறது, அளவுக்கதிக வேலையை பல்லுருப்புக்குணக் வேலையாக்குகிறது.

## நினைவகம் (மேல்-கீழ்)

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

## அட்டவணைமை (கீழ்-மேல்)

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

## நினைவகம் மற்றும் அட்டவணைமையை ஒப்பிடுதல்

| | நினைவகம் | அட்டவணைமை |
|---|------------|------------||
| திசை | மேல்-கீழ் சுழல்விதி | கீழ்-மேல் மீண்டுதல் |
| கணக்கிடுகிறது | தேவையான நிலைகள் மட்டுமே | அனைத்து நிலைகள் |
| ஆபத்து | stack overflow | இல்லை |
| இடம் | வெட்டப்பட முடியும் | பெரும்பாலும் O(1) வரிசையாக குறையக்கூடியது |

## சிக்கலின் அளவு

Fibonacci: O(2ⁿ) பாவனையற்றிலிருந்து **O(n)** கால, O(n) (அல்லது O(1)) இடம்.

## எப்போது பயன்படுத்த வேண்டும் / குறைபாடுகள்

துணைச் சிக்கல்கள் **மீண்டும் உள்ளன** போது DP ஐ பயன்படுத்தவும். நிலை மற்றும் மீண்டும் வாக்கியத்தை கவனத்துடன் குறிப்பிடவும் — அதுவே கடினமான பகுதி. துணைச் சிக்கல்கள் மீண்டும் இல்லாவிட்டால், எளிய பகுத்து வெல் போதுமானது.

## ஏன் முக்கியம்?

DP வெளிப்படையாக நிர்ணயிக்க முடியாத அளவுக்கதிக சிக்கல்களை — குறுகிய பாதைகள், திருத்த தூரம், பையாக — திறமையாக மாற்றுகிறது।

நிலை மற்றும் மீண்டுமை இருபந்தை தட்டிப் பிடிக்கும் திறமை அல்கோரிதம் நேர்காணல்களில் மிகவும் மதிக்கப்படுகிறது।

இது diff கருவிகளிலிருந்து இயற் தகவலியல் வரிசை சீரமைப்பு வரை உண்மையான முறைமைகளை அடிப்படையாகக் கொண்டுள்ளது।