Dynamic programming: state, transition और reconstruction
संबंध और लक्ष्य
Greedy पाठ का coin counterexample तथा runtime analysis आधार हैं। DP reusable subproblem answers निकालता है। State का सटीक अर्थ, exhaustive transition, base cases, dependency के अनुसार order और final answer जरूरी हैं। Repeated subproblems से reuse का लाभ; optimal substructure से optimal answers जोड़ना सही होता है।
1. Formula से पहले state
Unlimited positive integer denominations C और nonnegative integer target A लें। Exactly A बनाने में minimum coins चाहिए। D[x]=exact amount x का minimum coin count। D[0]=0; बाकी शुरुआत में ∞। x=1,...,A के लिए:
D[x]=min over c in C, c<=x of (1+D[x−c]); unreachable predecessor छोड़ें।
Candidate न मिले तो ∞। Positive coins से x−c<x, इसलिए increasing x सही dependency order। Answer D[A] है, पूरे table का minimum नहीं। Zero amount को zero coins; हर state zero initialize करने से unreachable amounts के झूठे solutions बनेंगे।
2. Transition का proof
Exact x के किसी nonempty optimum का अंतिम coin c है। उसे हटाने पर x−c का solution बचता है। Remainder minimum न हो तो उससे बेहतर remainder लगाकर original सुधार सकते हैं, जो contradiction है। इसलिए optimum किसी transition candidate में है। उलटे हर reachable predecessor में c जोड़ने से valid exact-x solution बनता है। Minimum attainable और optimal है। x पर induction पूरा table सिद्ध करता है।
3. पूरी छोटी table
C={1,3,4}, A=6 पर D[0..6]=[0,1,2,1,1,2,2]। x=5 में c=1,3,4 candidates: 1+D[4]=2, 1+D[2]=3, 1+D[1]=2; answer 2। x=6 पर 3,2,3; coin 3 चुनकर count 2। Greedy का 4+1+1 खराब है।
C={3,4}, A=2 पर D[1]=D[2]=∞। Zero coins न बताएँ और negative index न पढ़ें। Integer code में infinity+1 overflow से बचें: reachability check और safe sentinel लें। Positive integer coins के लिए A+1 sentinel चल सकता है, यदि वह numeric type में representable हो।
4. वास्तविक coins निकालें
Candidate strictly improve करे तो choice[x]=c भी save करें। Reachable A से x=A लें, choice[x] output करें और x=x−choice[x] करें; x=0 पर रुकें। Amount 6 पर 3 फिर 3 मिलता है। Ties consistent किसी भी तरह तोड़ सकते हैं; optimal count समान, list अलग हो सकती है। पहले D[A] finite जाँचें। Positive coins reconstruction terminate कराते हैं।
5. Time, memory और top-down
A+1 states, हर state पर k denominations: O(Ak) time, O(A) table/choice storage। Reconstruction output coins की संख्या जितना समय लेता है। यह A में pseudo-polynomial है: target का binary input केवल Θ(log A) bits है, इसलिए O(Ak) सामान्यतः input bit-length में polynomial नहीं।
Memoized top-down वही state/transition और solved amounts cache करता है; कुछ unneeded states बच सकते हैं। Base cases फिर भी जरूरी; बिना memoization repeated subproblems exponential work दे सकते हैं। Bottom-up recursive depth हटाता है। दोनों गलत state definition अपने-आप ठीक नहीं करते। Unlimited-coin state 0/1 usage नहीं संभालता; remaining items track करने होंगे, जैसा अगले पाठ में है।
मौलिक अभ्यास: छह single-correct MCQ
ये मौलिक शिक्षण प्रश्न हैं, पिछले वर्षों के प्रश्न नहीं। ठीक एक उत्तर चुनें।
P01. Exact minimum-coin DP में D[0]:
A. ∞ B. −1 C. 0 D. 1
उत्तर: C
A: Zero reachable है।
B: Count negative नहीं।
C: Empty selection amount zero बनाता है।
D: Coin नहीं चाहिए।
P02. C={1,3,4}, target 6: minimum count?
A. 1 B. 2 C. 3 D. 6
उत्तर: B
A: 6 denomination नहीं।
B: 3+3 में दो।
C: यह greedy answer है।
D: छह ones minimum नहीं।
P03. Increasing amount evaluation order सही क्यों?
A. सभी denominations समान B. Positive c से x−c छोटा है C. सभी answers zero D. Greedy ने हल कर दिया
उत्तर: B
A: Denominations अलग हो सकते हैं।
B: Dependencies पहले evaluate हो चुकी हैं।
C: केवल zero base zero है।
D: DP greedy failure सुधारता है।
P04. C={3,4}, target 2 का result:
A. 0 coins B. 1 coin C. 2 coins D. Unreachable
उत्तर: D
A: Zero coins zero बनाते हैं।
B: कोई denomination दो नहीं।
C: दो coins कम-से-कम छह हैं।
D: कोई combination दो नहीं बनाता।
P05. Reconstruction के लिए सीधे क्या save करें?
A. केवल target A B. हर improved state का chosen coin C. केवल runtime D. केवल denominations की संख्या
उत्तर: B
A: Target transition नहीं बताता।
B: Choices से predecessor amounts मिलते हैं।
C: Runtime solution path नहीं।
D: Denomination count coins नहीं बताता।
P06. Binary-encoded target A पर O(Ak) कहलाता है:
A. हमेशा constant B. Pseudo-polynomial C. A में हमेशा exponential D. A से स्वतंत्र
उत्तर: B
A: A,k पर निर्भर है।
B: A अपनी bit-length में exponential हो सकता है।
C: Fixed k पर A में linear है।
D: A explicit factor है।
स्रोत और दायरा
यह 2026 course के बताए भाग का पाठ है, पूरे Algorithms syllabus की समाप्ति नहीं। सभी गणनात्मक उदाहरण और प्रश्न मौलिक हैं। 2027 की पूर्णता का दावा नहीं।
प्रगति सहेजने के लिए साइन इन करें। साइन इन