गुब्बारे फोड़ना: उलटा अंतराल DP
हर अंतराल में पहले गुब्बारे के बजाय आखिरी गुब्बारा फोड़ने का चयन करते हुए, समस्या को उलटे दृष्टिकोण से हल कीजिए।
गुब्बारे फोड़ना: उलटा अंतराल DP, CoddyKit पर कोडिंग साक्षात्कार की तैयारी का एक निःशुल्क पाठ है। यह 4 में से 4वाँ पाठ है। आप नीचे पूरा पाठ निःशुल्क पढ़ सकते हैं—फिर अंतर्निहित कोड संपादक और 24/7 एआई ट्यूटर के साथ ब्राउज़र में इसका व्यावहारिक अभ्यास कर सकते हैं। यह कोडिंग साक्षात्कार की तैयारी सीखने के मार्ग का हिस्सा है और आपकी प्रगति वेब तथा CoddyKit ऐप पर सिंक होती रहती है। कोडिंग साक्षात्कार की तैयारी पाठ्यक्रम में कुल 4 पाठ शामिल हैं।
गुब्बारे फोड़ने की समस्या
nums मान वाले n गुब्बारे दिए गए हैं। गुब्बारा i फोड़ने पर nums[i-1] * nums[i] * nums[i+1] सिक्के मिलते हैं (अर्थात् उसके अपने मान और उस समय के पड़ोसी गुब्बारों का गुणनफल)। सभी गुब्बारे फोड़कर प्राप्त किए जा सकने वाले अधिकतम सिक्के ज्ञात करें। सीधा अनुकरण कठिन है, क्योंकि गुब्बारा फोड़ने से पड़ोसी बदल जाते हैं — उल्टे क्रम वाला अंतराल DP इस कठिनाई को कुशलता से दूर करता है।
आगे का अनुकरण क्यों विफल होता है
यदि हम dp[i][j] को [i, j] सीमा में गुब्बारे फोड़ने से मिलने वाले अधिकतम सिक्कों के रूप में परिभाषित करें और सोचें कि पहले कौन-सा गुब्बारा फोड़ना है, तो एक समस्या आती है: गुब्बारा k पहले फोड़ने का अर्थ है कि nums[k-1] और nums[k+1] उस समय के पड़ोसी होने चाहिए — लेकिन इन गुब्बारों को बाद में फोड़ा जा सकता है, जिससे पड़ोसी गतिशील रूप से बदलते रहेंगे। आगे की दिशा में अवस्था को साफ़-सुथरे ढंग से परिभाषित करना कठिन है।
मुख्य अंतर्दृष्टि: उल्टा सोचिए
युक्ति यह है कि [i, j] अंतराल में सबसे अंतिम गुब्बारा कौन-सा फोड़ा जाएगा, इस पर विचार करें। जब गुब्बारा k, [i, j] में आखिरी बार फोड़ा जाता है, तब [i, j] के बाकी सभी गुब्बारे पहले ही हट चुके होते हैं। इसलिए गुब्बारे k के पड़ोसी ठीक nums[i-1] और nums[j+1] होते हैं — यानी अंतराल के ठीक बाहर स्थित सीमावर्ती गुब्बारे। इससे अंतिम बार फोड़ने पर मिलने वाले सिक्कों की गणना निश्चित हो जाती है: यह पहले किए गए विस्फोटों के क्रम पर निर्भर नहीं करती।
अवस्था और पुनरावृत्ति की परिभाषा
प्रहरी गुब्बारे जोड़ें: nums के आगे और पीछे 1 जोड़कर nums = [1] + nums + [1] बनाएँ। dp[i][j] को उन सभी गुब्बारों को फोड़ने से मिलने वाले अधिकतम सिक्कों के रूप में परिभाषित करें जो सूचकांकों i और j के बीच सख्ती से स्थित हैं (अर्थात् दोनों सिरों को छोड़कर), जहाँ nums[i] और nums[j] बचे हुए सीमावर्ती गुब्बारे हैं। पुनरावृत्ति: (i, j) में प्रत्येक संभावित अंतिम गुब्बारे k के लिए: dp[i][j] = max(dp[i][k] + dp[k][j] + nums[i]*nums[k]*nums[j])।
# With sentinels: nums = [1] + original + [1]
# dp[i][j] = max coins from bursting all balloons in open interval (i, j)
# k = last balloon to burst in (i,j)
# dp[i][j] = max over k in (i,j): dp[i][k] + dp[k][j] + nums[i]*nums[k]*nums[j]पूर्ण कार्यान्वयन
हम सारणी में प्रहरी जोड़ते हैं, DP तालिका को शून्य से आरंभ करते हैं (खाली अंतराल = 0 सिक्के), और बढ़ती हुई अंतराल लंबाई के क्रम में उसे भरते हैं। अंतिम उत्तर dp[0][n+1] है, जो सभी मूल गुब्बारों को फोड़ने पर मिलने वाले अधिकतम सिक्कों को दर्शाता है, जहाँ प्रहरी स्थायी सीमाओं के रूप में काम करते हैं।
def maxCoins(nums):
nums = [1] + nums + [1]
n = len(nums)
dp = [[0]*n for _ in range(n)]
# length of open interval (i, j) exclusive: j - i - 1 balloons inside
for length in range(2, n): # length = j - i
for i in range(0, n - length):
j = i + length
for k in range(i+1, j): # k is last burst in (i, j)
coins = dp[i][k] + dp[k][j] + nums[i]*nums[k]*nums[j]
dp[i][j] = max(dp[i][j], coins)
return dp[0][n-1]
print(maxCoins([3, 1, 5, 8])) # 167उदाहरण का क्रमिक विवेचन
[3, 1, 5, 8] के लिए, प्रहरी जोड़ने पर [1, 3, 1, 5, 8, 1] मिलता है (सूचकांक 0-5)। हमें dp[0][5] चाहिए। लंबाई=2 वाले अंतरालों के लिए (अंदर एक गुब्बारा): dp[0][2] = 1*3*1=3, dp[1][3]=3*1*5=15, dp[2][4]=1*5*8=40, dp[3][5]=5*8*1=40। आगे की गणनाएँ करने पर सर्वोत्तम क्रम यह है कि {3,1,5,8} में 1 को सबसे अंत में फोड़ा जाए और उसके पड़ोसियों को पहले फोड़ा जाए; इससे कुल 167 सिक्के मिलते हैं।
जटिलता का विश्लेषण
O(n²) अंतराल होते हैं और प्रत्येक अंतराल के लिए O(n) विभाजन-बिंदु आज़माए जाते हैं, इसलिए O(n³) समय जटिलता मिलती है। DP तालिका के लिए स्थान O(n²) है। n = 500 गुब्बारों के लिए यह 12.5 करोड़ संक्रियाएँ हैं — साक्षात्कार की सीमाओं के लिए संभव। प्रहरी जोड़ने से सीमाओं को संभालना सरल हो जाता है: इनके बिना यह जाँच करनी पड़ती कि i-1 और j+1 वैध सीमा में हैं या नहीं।
स्मृति-संग्रहीत टॉप-डाउन विकल्प
यही समाधान @lru_cache के साथ टॉप-डाउन तरीके से भी लिखा जा सकता है, जिसे साक्षात्कार के दौरान निकालना अधिक सहज लग सकता है। solve(i, j) को खुले अंतराल (i, j) में मिलने वाले अधिकतम सिक्कों के रूप में परिभाषित करें। यह फ़ंक्शन सभी k को अंतिम बार फोड़े जाने वाले गुब्बारे के रूप में आज़माता है और परिणामों को स्मृति में रखता है। दोनों विधियों की समय और स्थान जटिलता समान है।
from functools import lru_cache
def maxCoins_memo(nums):
nums = [1] + nums + [1]
n = len(nums)
@lru_cache(maxsize=None)
def solve(i, j):
if j - i < 2: # no balloons between i and j
return 0
return max(
solve(i, k) + solve(k, j) + nums[i]*nums[k]*nums[j]
for k in range(i+1, j)
)
return solve(0, n-1)
print(maxCoins_memo([3, 1, 5, 8])) # 167सामान्य भूल: आगे की दिशा में DP की परिभाषा
एक सामान्य भूल dp[i][j] को [i,j] में पहले गुब्बारे को फोड़ने पर मिलने वाले सिक्कों के रूप में परिभाषित करना है, न कि अंतिम गुब्बारे के रूप में। यह इसलिए विफल होता है क्योंकि पहले गुब्बारे के सिक्कों की गणना उन पड़ोसी गुब्बारों पर निर्भर करती है जिन्हें अभी नहीं फोड़ा गया है — और एल्गोरिदम के आगे बढ़ने पर उन पड़ोसियों की अवस्था बदलती रहती है। जब सीमाएँ बचे हुए अवयवों पर निर्भर हों, तो अंतराल DP में हमेशा अंतिम अवयव के बारे में सोचें।
1 के प्रहरी मान क्यों?
1 के प्रहरी मान इसलिए चुने जाते हैं क्योंकि वे गुणा के लिए तटस्थ अवयव की तरह काम करते हैं। जब कोई सीमावर्ती गुब्बारा अंतिम बार फोड़ा जाता है, तो उसके सिक्कों का मान boundary * last * boundary = 1 * last * 1 = last होता है। 0 का उपयोग करने पर 0 सिक्के मिलेंगे (जो गलत है), जबकि अन्य मानों का उपयोग करने पर गणना विकृत हो जाएगी। प्रहरी की यह युक्ति बाएँ और दाएँ छोर के गुब्बारों के लिए अलग-अलग मामले सँभाले बिना सभी सीमांत मामलों को साफ़-सुथरे ढंग से एकीकृत करती है।
मानक अंतराल DP से तुलना
मानक अंतराल DP (मैट्रिक्स शृंखला) में विभाजन-बिंदु k दर्शाता है कि समस्या को दो उपसमस्याओं में कहाँ बाँटा जाए, जिन्हें स्वतंत्र रूप से हल किया जाता है। Burst Balloons में k अंतराल में सबसे अंत में फोड़ा जाने वाला गुब्बारा है, इसलिए [i,k] और [k,j] के दोनों उप-अंतराल स्वतंत्र हो जाते हैं, क्योंकि k अभी भी एक सीमा के रूप में मौजूद है। यही उल्टा दृष्टिकोण वह रचनात्मक अंतर्दृष्टि है जो गुब्बारे फोड़ने की समस्या को अंतराल DP से हल करने योग्य बनाती है।
त्वरित जाँच
इस पाठ में दिए गए डेटा संरचनाएँ और एल्गोरिदम — कोडिंग इंटरव्यू तैयारी संबंधी अवधारणाओं की अपनी समझ जाँचें।
पाठ का पुनरावलोकन
इस पाठ में आपने सीखा: आगे की दिशा में अनुकरण विफल होता है क्योंकि बैलून फोड़ने से पड़ोसी अप्रत्याशित रूप से बदल जाते हैं, उल्टी दिशा वाली अंतर्दृष्टि k को किसी अंतराल में अंत में फोड़े जाने वाले बैलून के रूप में परिभाषित करती है, जिससे पड़ोसी nums[i] और nums[j] बनते हैं, और सेंटिनल पैडिंग के साथ पुनरावृत्ति dp[i][j] = max(dp[i][k] + dp[k][j] + nums[i]*nums[k]*nums[j]) O(n³) समाधान देती है। अगले पाठ में हम नैपसैक DP की ओर बढ़ेंगे, जिसकी शुरुआत पारंपरिक 0/1 नैपसैक और उसके स्थान-अनुकूलन से होगी।
एआई शिक्षक के साथ कोडिंग साक्षात्कार की तैयारी सीखें — निःशुल्क
अपने ब्राउज़र में वास्तविक कोड लिखें और चलाएँ, चौबीसों घंटे एआई शिक्षक से तुरंत सहायता पाएँ, और वेब या ऐप पर वहीं से शुरू करें जहाँ आपने छोड़ा था।
- पाठ्यक्रम
- 90
- पाठ
- 360
अक्सर पूछे जाने वाले प्रश्न
क्या “गुब्बारे फोड़ना: उलटा अंतराल DP” पाठ निःशुल्क है?
हाँ—“गुब्बारे फोड़ना: उलटा अंतराल DP” का पूरा पाठ यहाँ वेब पर निःशुल्क पढ़ा जा सकता है। इंटरैक्टिव अभ्यास (अंतर्निहित कोड संपादक और 24/7 एआई ट्यूटर) करने और कोडिंग साक्षात्कार की तैयारी पाठ्यक्रम का बाकी हिस्सा अनलॉक करने के लिए CoddyKit PRO लें। कोडिंग साक्षात्कार की तैयारी पाठ्यक्रम में कुल 4 पाठ शामिल हैं।
“गुब्बारे फोड़ना: उलटा अंतराल DP” में मैं क्या सीखूँगा?
हर अंतराल में पहले गुब्बारे के बजाय आखिरी गुब्बारा फोड़ने का चयन करते हुए, समस्या को उलटे दृष्टिकोण से हल कीजिए। आप ब्राउज़र में सीधे चलाए जाने वाले व्यावहारिक कोड के साथ कोडिंग साक्षात्कार की तैयारी का अभ्यास करते हैं, और पाठ पूरा करते समय 24/7 एआई ट्यूटर आपके प्रश्नों के उत्तर देता है।
क्या कोडिंग साक्षात्कार की तैयारी शुरू करने के लिए मुझे किसी अनुभव की आवश्यकता है?
पहले के अनुभव की आवश्यकता नहीं है। CoddyKit पर कोडिंग साक्षात्कार की तैयारी शुरुआती से लेकर उन्नत शिक्षार्थियों तक सभी के लिए व्यवस्थित किया गया है, इसलिए आप यहीं से या शुरुआत से सीखना शुरू कर सकते हैं और अपनी गति से आगे बढ़ सकते हैं। यह 4 में से 4वाँ पाठ है।
“गुब्बारे फोड़ना: उलटा अंतराल DP” पाठ पूरा करने में कितना समय लगता है?
CoddyKit का अधिकांश पाठ लगभग 5–10 मिनट में पूरा हो जाता है। हर पाठ छोटा और संवादात्मक है, इसलिए आप लगातार प्रगति करते हैं और वेब या ऐप पर वहीं से सीखना जारी रख सकते हैं जहाँ आपने छोड़ा था।
क्या मैं इस कोडिंग साक्षात्कार की तैयारी पाठ में कोड लिख और चला सकता हूँ?
हाँ। हर कोडिंग साक्षात्कार की तैयारी पाठ में एक अंतर्निर्मित कोड संपादक शामिल है, जिससे आप सीधे अपने ब्राउज़र में वास्तविक कोड लिख और चला सकते हैं और तुरंत एआई प्रतिक्रिया पा सकते हैं—स्थानीय सेटअप की आवश्यकता नहीं है।
इस पाठ्यक्रम के सभी पाठ
- अंतराल DP पैटर्न और भरने का क्रम
- सबसे लंबा पैलिंड्रोमिक उपअनुक्रम और सबस्ट्रिंग
- पैलिंड्रोम विभाजन II
- गुब्बारे फोड़ना: उलटा अंतराल DP