पाठ · #11 / 11

डायनामिक प्रोग्रामिंग (Dynamic Programming)

समय के बदले मेमोरी — एक बार हल करो, हमेशा के लिए याद रखो

Dynamic programming · 1D table fill

…

speed step 0 / 0

आज़माएँ: 1-D टेबल को बाएँ से दाएँ भरते हुए देखें — हर सेल बस अपने पहले की दो सेल का योग है। जिस मान को नैव रिकर्शन अरबों बार दोबारा गिनता, वह बग़ल वाली सेल से एक ही बार पढ़ लिया जाता है। यही पूरा विचार है: दोबारा गिनना → देख लेना।

यह क्यों मायने रखता है

हैरतअंगेज़ रूप से बहुत-सी "घातांकी (exponential)" समस्याएँ दरअसल छुपे तौर पर बहुपदी (polynomial) होती हैं — वे सिर्फ़ घातांकी लगती हैं क्योंकि उनकी सीधी रिकर्शन एक ही उप-समस्या को लाखों बार हल करती है। डायनामिक प्रोग्रामिंग वह तकनीक है जो दोहराव को पहचानकर उसे कैश कर लेती है। एक बार पैटर्न दिख जाए, तो जिन समस्याओं में सदियाँ लगतीं, वे ढहकर मिलीसेकंड में सिमट जाती हैं।

रोबोटिक्स में यह value iteration, policy iteration, Bellman रिकर्शन, और उन सबसे छोटे-पथ एल्गोरिथ्म की बुनियाद है जिनसे आप पहले मिल चुके हैं। string में यह वह diff एल्गोरिथ्म है जो git इस्तेमाल करता है। bioinformatics में हर sequence-alignment औज़ार इसी तरह काम करता है।

मूल विचार

DP-आकार की समस्या में दो गुण होते हैं:

Optimal substructure — पूरी समस्या का इष्टतम (optimal) जवाब उसी समस्या के छोटे संस्करणों के इष्टतम जवाबों से बनाया जा सकता है।
Overlapping subproblems — वे छोटे संस्करण दोहराते हैं। भोली रिकर्शन एक ही को कई बार हल करेगी।

जब दोनों टिकते हैं, तो तरकीब है हर उप-समस्या को ठीक एक बार हल करना और नतीजा सहेज लेना। दो रूप:

Memoization (top-down): रिकर्शन रखो; हर कॉल का return मान कैश करो। पहली बार जब आप f(7) पर पहुँचते हैं तो उसे गणना करते हैं; उसके बाद आप कैश से पढ़ लेते हैं।
Tabulation (bottom-up): रिकर्शन पूरी तरह छोड़ दो। सबसे छोटी उप-समस्याओं से लेकर पूरी समस्या तक एक ऐरे (या 2-D टेबल) भरो। हर कोशिका का मान उन कोशिकाओं का एक फलन है जिन्हें आप पहले ही भर चुके हैं।

दोनों O(states × per-state-work) हैं। Memoization स्वाभाविक पुनरावृत्ति (recurrence) के क़रीब है; tabulation आपको जगह और क्रम पर ज़्यादा बारीक नियंत्रण देता है।

मुख्य बातें

DP = रिकर्शन + एक कैश जो पक्का करता है कि हर उप-समस्या एक बार हल हो।
सबसे मुश्किल हिस्सा है state ढूँढना — f(i, j, k…) को अपना जवाब देने के लिए क्या जानना ज़रूरी है?
एक बार recurrence सही हो जाए, तो समय जटिलता (states की संख्या) × (प्रति state काम) होती है।
1D समस्याएँ अक्सर सिर्फ़ आख़िरी कुछ कोशिकाएँ रखकर (rolling) O(n) जगह से ढहकर O(1) हो जाती हैं।
2D समस्याएँ अक्सर एक बार में सिर्फ़ एक पंक्ति रखकर O(m·n) से ढहकर O(min(m, n)) हो जाती हैं।

और गहराई में

DP आकार पहचानना

किसी भी समस्या से, जिस पर DP का शक हो, ये पाँच सवाल पूछिए:

क्या मैं जवाब को रिकर्सिव रूप से बता सकता हूँ? "state X तक पहुँचने की न्यूनतम लागत, Y विकल्पों के न्यूनतम के बराबर है …"
state क्या है? एक अकेला पूर्णांक? एक जोड़ा (i, j)? एक इंडेक्स और एक झंडा (flag)?
recurrence क्या है? f(state) कैसे f(smaller-state) में विघटित होता है?
base case क्या हैं? वे सबसे छोटे state जिनका जवाब बिना रिकर्शन के ज्ञात है।
टेबल किस क्रम में भरूँ? कोई भी क्रम जहाँ हर कोशिका की निर्भरताएँ उससे पहले भर जाएँ।

अगर आप पाँचों का जवाब दे सकें, तो आप DP लिख सकते हैं। अगर नहीं, तो आपके पास अभी DP समस्या है ही नहीं — दोबारा बयान कीजिए।

Memoization बनाम tabulation — किसे कब चुनें

| | Memoization | Tabulation | |---|---|---| | मानसिक मॉडल | Top-down: रिकर्शन पर भरोसा करो | Bottom-up: टुकड़ा-टुकड़ा बनाओ | | क्रियान्वयन | रिकर्सिव फ़ंक्शन + कैश | एक ऐरे भरता लूप | | हल हुई उप-समस्याएँ | सिर्फ़ वे जो पहुँच में हैं | सब की सब | | स्टैक का ख़तरा | गहरी रिकर्शन → स्टैक ओवरफ़्लो | कोई नहीं | | जगह-अनुकूलन की संभावना | मुश्किल | आसान (rolling पंक्तियाँ / "आख़िरी दो मान") |

Memoization चुनिए जब state space विरल (sparse) हो — कई state मौजूद हों पर जवाब सिर्फ़ एक छोटे पहुँच-योग्य समुच्चय पर निर्भर हो। Tabulation चुनिए जब आप वैसे भी ज़्यादातर state space छूने वाले हों, या जब आपको जगह-अनुकूलन करना हो।

जगह-अनुकूलन — "rolling" तरकीब

ज़्यादातर DP recurrence सिर्फ़ एकदम पिछली पंक्ति या स्थिर-कितनी पिछली कोशिकाओं पर निर्भर करते हैं। तो आपको पूरी टेबल की ज़रूरत नहीं।

Fibonacci को सिर्फ़ f(n-1) और f(n-2) चाहिए → O(1) जगह।
m × n पर LCS सिर्फ़ पिछली पंक्ति पर निर्भर है → O(min(m, n)) जगह।
Knapsack को सिर्फ़ पिछला capacity कॉलम चाहिए → O(W) जगह।

recurrence पर नज़र रखिए: अगर छोटे k के लिए f(i) सिर्फ़ f(i-1), f(i-2), …, f(i-k) इस्तेमाल करता है, तो आप बस उन्हीं k मानों को रखकर सरकते रह सकते हैं।

रोबोटिक्स लंगर — DP ही Bellman है, ही value iteration है

रीइन्फ़ोर्समेंट लर्निंग में Bellman समीकरण सचमुच एक DP recurrence है:

V*(s) = max over actions a of [ R(s, a) + γ · Σ P(s' | s, a) · V*(s') ]

state s का इष्टतम मान, तत्काल इनाम (reward) जमा सबसे अच्छे अगले state के घटाए (discounted) भावी मान के बराबर है। Value iteration बस state space पर Bellman recurrence का tabulation है, जो अभिसरण (convergence) तक दोहराया जाता है। हर gridworld solver, हर path-planner जो लागतें सँभालता है, पाठ्यपुस्तक का हर MPC नियंत्रक — सब DP हैं।

जब DP नाकाम होता है

DP को optimal substructure चाहिए। कुछ समस्याएँ इसका उल्लंघन करती हैं:

किसी आम ग्राफ़ में longest simple path (कोई DP नहीं — NP-hard)।
कुछ भी जहाँ भावी चुनाव पूरे इतिहास पर निर्भर हों, न कि किसी सारांश-योग्य state पर।

अगर आपको ऐसा कोई परिमित (finite) state न मिले जो वह सब समेट ले जो भावी क़दमों को जानना ज़रूरी है, तो DP लागू नहीं होता।

असल दुनिया में

Diff एल्गोरिथ्म (git diff, diff -u) O(m·n) में longest common subsequence निकालते हैं — ठीक नीचे की तीसरी समस्या।
अनिश्चितता के तहत रोबोट नियोजन value iteration / policy iteration इस्तेमाल करता है — दोनों state space पर शुद्ध DP।
कम्प्यूटेशनल जीव-विज्ञान में Sequence alignment (Needleman-Wunsch, Smith-Waterman) एक 2-D edit टेबल पर DP है।
वाक्-पहचान (speech recognition) का Viterbi एल्गोरिथ्म छुपे state का सबसे संभावित अनुक्रम ढूँढता है — एक trellis पर DP।
कंपाइलर register allocation अभिव्यक्ति-वृक्षों पर DP इस्तेमाल करता है।
Routing protocol (OSPF, BGP path selection) — Bellman-Ford ग्राफ़ दूरियों पर DP है।

गणितीय ब्यौरा

Time: O(states × work-per-state) — एक बार आपने state निरूपण चुन लिया, तो यह ठीक-ठीक यही है।
Space (full table): O(states)
Space (rolling): अक्सर O(d) जहाँ d recurrence की "lookback depth" है — आम तौर पर एक छोटा स्थिरांक या एक पंक्ति।
Memoization overhead: HashMap lookup + रिकर्शन स्टैक — एक तंग tabulation लूप के मुक़ाबले 2-3× का स्थिर गुणांक। विरल state space के लिए चुकाने लायक़।

क्रियान्वयन (Implementation)

कंकाल — हर DP इस टेम्पलेट में अँटता है

def solve():
    memo = {}
    def f(state):
        if state in BASE_CASES: return base_answer
        if state in memo: return memo[state]
        result = combine(f(smaller_state_1), f(smaller_state_2), ...)
        memo[state] = result
        return result
    return f(initial_state)

या, tabulated:

def solve():
    dp = [base_answer for _ in range(N + 1)]
    for state in range(SMALLEST + 1, LARGEST + 1):
        dp[state] = combine(dp[smaller_1], dp[smaller_2], ...)
    return dp[LARGEST]

चिर-परिचित समस्या-आकार

1D linear: f(n) = combine(f(n-1), f(n-2)) — Fibonacci, climb stairs, house robber
1D unbounded: f(amount) = min over coins of f(amount - coin) + 1 — coin change, rod cutting
2D: f(i, j) = combine(f(i-1, j), f(i, j-1), f(i-1, j-1)) — LCS, edit distance, grid paths
Intervals: f(i, j) = min over splits k of f(i, k) + f(k, j) + cost(i, j, k) — matrix-chain, optimal BST
Tree DP: post-order traversal, हर नोड का जवाब उसके बच्चों से गढ़ा — diameter, max-path-sum

अभ्यास

तीन समस्याएँ जो तीन बुनियादी DP आकारों को पक्का कर देती हैं:

Climb Stairs — आसान · 1D Fibonacci-आकार; memoization → tabulation → O(1)-जगह वाली प्रगति
Coin Change — मध्यम · 1D unbounded knapsack; "विकल्पों का न्यूनतम" recurrence
Longest Common Subsequence — मध्यम · 2D टेबल; हर diff औज़ार की बुनियाद

→ सभी अभ्यास सवाल देखें

🧮 डायनामिक प्रोग्रामिंग (Dynamic Programming)