DP ਅਤੇ greedy ਦੋਵਾਂ ਨੂੰ optimal substructure ਦੀ ਲੋੜ ਹੁੰਦੀ ਹੈ। ਫਰਕ: greedy ਨੂੰ greedy-choice property ਵੀ ਚਾਹੀਦੀ ਹੈ (ਇੱਕ local optimum globally optimal ਹੈ), ਜਦਕਿ DP ਦੀ ਲੋੜ ਉਦੋਂ ਹੈ ਜਦੋਂ ਤੁਹਾਨੂੰ ਮਲਟੀਪਲ choices ਅਤੇ overlapping subproblems 'ਤੇ ਵਿਚਾਰ ਕਰਨਾ ਪਏ।
Optimal substructure? -- both need this
+ greedy-choice property holds? -> GREEDY (fast, one pass of choices)
+ must compare many sub-solutions / they overlap? -> DYNAMIC PROGRAMMING
# Greedy FAILS for coins {1,3,4}, amount 6 -> 4+1+1 (3 coins)
# DP finds the true optimum: 3+3 (2 coins)
def min_coins(amount, coins):
INF = float('inf')
dp = [0] + [INF] * amount
for a in range(1, amount + 1):
for c in coins:
if c <= a:
dp[a] = min(dp[a], dp[a - c] + 1) # try every coin
return dp[amount]
min_coins(6, [1, 3, 4]) # -> 2
Greedy ਇੱਕ choice ਕਮਿਟ ਕਰਦਾ ਹੈ; DP ਸਭ explore ਕਰਦਾ ਹੈ ਅਤੇ ਸਭ ਤੋਂ ਵਧੀਆ ਰੱਖਦਾ ਹੈ।
Greedy ਆਮ ਤੌਰ 'ਤੇ O(n log n) ਹੁੰਦਾ ਹੈ; DP ਵਧੇਰੇ time/space (ਅਕਸਰ O(n·m)) ਨੂੰ correctness ਲਈ trade ਕਰਦਾ ਹੈ।
Greedy ਨੂੰ ਇਸ ਦੀ property ਸਿੱਧ ਕੀਤੇ ਬਿਨਾਂ ਵਰਤਣਾ ਗਲਤ ਜਵਾਬ ਦਿੰਦਾ ਹੈ ਜੋ ਛੋਟੀਆਂ ਟੈਸਟਾਂ ਪਾਸ ਕਰਦੇ ਹਨ। ਸ਼ੰਕਾ ਵਿੱਚ, DP ਲਈ ਪਹੁੰਚ ਕਰੋ ਜਾਂ greedy ਨੂੰ brute force ਨਾਲ verify ਕਰੋ।
Greedy ਚੁਣਨਾ ਜਦੋਂ ਇਹ ਵੈਧ ਹੋ ਤਾਂ ਬਹੁਤ ਸਮਾਂ ਬਚਾਉਂਦਾ ਹੈ; ਇਸਨੂੰ ਚੁਣਨਾ ਜਦੋਂ ਅਸਫ ਹੋ ਤਾਂ silent bugs ਪੈਦਾ ਕਰਦਾ ਹੈ।
Jani paradigm fit ਕਰਦਾ ਹੈ ਜਾਣਨਾ — ਅਤੇ ਇਸ ਨੂੰ ਸਿੱਧ ਕਰਨ ਦੀ ਯੋਗਤਾ — ਇੱਕ senior-level ਵਿਸ਼ਲੇਸ਼ਣ ਹੈ।
ਇਹ DP ਨਾਲ over-engineering ਦੋਵਾਂ ਤੋਂ ਵਿਰਾਮ ਦਿੰਦਾ ਹੈ ਅਤੇ ਇੱਕ unsound greedy choice ਨਾਲ under-delivering ਕਰਦਾ ਹੈ।
ਵਿਸਤ੍ਰਿਤ ਜਵਾਬਾਂ ਨਾਲ IT ਇੰਟਰਵਿਊ ਸਵਾਲਾਂ ਦੀ ਇੱਕ ਲਾਇਬ੍ਰੇਰੀ — ਜੂਨੀਅਰ ਤੋਂ ਸੀਨੀਅਰ ਤੱਕ।
ਦਾਨ ਕਰੋ