ਡਾਇਨਾਮਿਕ ਪ੍ਰੋਗ੍ਰਾਮਿੰਗ (DP) overlapping subproblems ਅਤੇ optimal substructure ਦੇ ਨਾਲ ਸਮੱਸਿਆਵਾਂ ਨੂੰ ਹੱਲ ਕਰਦੀ ਹੈ, ਹਰੇਕ subproblem ਨੂੰ ਇੱਕ ਵਾਰ ਗਣਨਾ ਕਰਕੇ ਅਤੇ ਨਤੀਜੇ ਨੂੰ ਦੁਬਾਰਾ ਵਰਤ ਕੇ। ਦੋ ਸ਼ੈਲੀਆਂ memoization (top-down) ਅਤੇ tabulation (bottom-up) ਹਨ।
ਭੋਲੀ recursion ਉਸੇ subproblems ਦੀ ਵਾਰ-ਵਾਰ ਗਣਨਾ ਕਰਦੀ ਹੈ। DP ਉਨ੍ਹਾਂ ਨੂੰ cache ਕਰਦਾ ਹੈ, exponential ਕੰਮ ਨੂੰ polynomial ਵਿੱਚ ਬਦਲ ਦਿੰਦਾ ਹੈ।
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
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]
| Memoization | Tabulation | |
|---|---|---|
| Direction | top-down recursion | bottom-up iteration |
| Computes | ਸਿਰਫ਼ ਲੋੜੀਂਦੀਆਂ states | ਸਾਰੀਆਂ states |
| Risk | stack overflow | ਕੋਈ ਨਹੀਂ |
| Space | ਘਟਾਇਆ ਜਾ ਸਕਦਾ ਹੈ | ਅਕਸਰ O(1) ਕਤਾਰਾਂ ਤੱਕ ਘਟਾਇਆ ਜਾ ਸਕਦਾ ਹੈ |
Fibonacci: O(2ⁿ) ਭੋਲੇ ਤੋਂ O(n) time, O(n) (ਜਾ O(1)) space ਤਕ।
DP ਵਰਤੋ ਜਦੋਂ subproblems overlap ਕਰਨ। state ਅਤੇ recurrence ਨੂੰ ਧਿਆਨ ਨਾਲ ਪਰਿਭਾਸ਼ਿਤ ਕਰੋ — ਇਹ ਮੁਸ਼ਕਲ ਹਿੱਸਾ ਹੈ। ਜੇ subproblems ਓਵਰਲੈਪ ਨਹੀਂ ਕਰਦੇ, ਤਾਂ ਸਾਧਾਰਣ divide-and-conquer ਕਾਫ਼ੀ ਹੈ।
DP intractable exponential ਸਮੱਸਿਆਵਾਂ — shortest paths, edit distance, knapsack — ਨੂੰ efficient ਵਿੱਚ ਤਬਦੀਲ ਕਰਦਾ ਹੈ।
state ਅਤੇ recurrence ਦੀ ਪਛਾਣ ਕਰਨ ਦੀ ਸਖ਼ਤੀ algorithm interviews ਵਿੱਚ ਸਭ ਤੋਂ ਵੱਧ ਮੂਲਵਾਨ ਹੈ।
ਇਹ diff tools ਤੋਂ bioinformatics sequence alignment ਤਕ ਅਸਲ ਸਿਸਟਮਾਂ ਦਾ ਆਧਾਰ ਹੈ।
ਵਿਸਤ੍ਰਿਤ ਜਵਾਬਾਂ ਨਾਲ IT ਇੰਟਰਵਿਊ ਸਵਾਲਾਂ ਦੀ ਇੱਕ ਲਾਇਬ੍ਰੇਰੀ — ਜੂਨੀਅਰ ਤੋਂ ਸੀਨੀਅਰ ਤੱਕ।
ਦਾਨ ਕਰੋ