Grid पर Paths गिनना

आप ग्रिड के ऊपरी-बाएँ कोने से शुरू करते हैं और निचले-दाएँ कोने तक पहुँचना चाहते हैं। हर कदम दाएँ या नीचे जाता है। कितने अलग-अलग पथ मौजूद हैं?

हर कोशिका तक उसके ऊपर वाली या बाईं ओर वाली कोशिका से पहुँचा जा सकता है। यही अतिव्यापन इस समस्या को ठीक DP समस्या बनाता है।

मान लीजिए dp[i][j] आरंभिक कोशिका से (i, j) कोशिका तक पहुँचने के तरीकों की संख्या है। अवस्था को स्पष्ट नाम देना आधी समस्या हल कर देता है।

आप केवल ऊपर या बाईं ओर से पहुँच सकते हैं, इसलिए संख्या उनका योग होगी। यही संक्रमण पूरी तालिका को संचालित करता है।

आरंभिक कोशिका तक पहुँचने का ठीक एक तरीका है: कुछ न करना। इसलिए बाकी कुछ भरने से पहले dp[0][0] का मान 1 होता है।

ऊपरी पंक्ति या बाएँ स्तंभ की कोशिकाओं तक पहुँचने का केवल एक सीधा मार्ग होता है। उनकी संख्या हमेशा 1 होती है, क्योंकि एक पड़ोसी ग्रिड के बाहर होता है।

शून्यों से भरी हुई m गुणा n तालिका बनाइए। पहले से आकार तय करने पर सूचकांक साफ़ रहते हैं और अनपेक्षित समस्याओं से बचा जा सकता है।

पहले पंक्तियों और फिर स्तंभों पर लूप चलाइए, ऊपर से नीचे और बाएँ से दाएँ। यह क्रम सुनिश्चित करता है कि उपयोग करने से पहले दोनों पड़ोसी तैयार हों।

भरने के बाद पथों की संख्या अंतिम कोशिका में होती है। उत्तर dp[m-1][n-1] है, जो निचले-दाएँ कोने पर स्थित है।

हर पंक्ति को केवल अपने ऊपर वाली पंक्ति की आवश्यकता होती है, इसलिए आप एक ही पंक्ति रखकर उसी में मान अद्यतन कर सकते हैं। इससे स्मृति O(n) तक घट जाती है।

जब कोई अवरोध न हो, तो उत्तर एक द्विपद गुणांक होता है: कुल कदमों में से नीचे जाने वाले कदम चुनिए। अवरोध आने पर भी DP उपयोगी रहता है।

dp को किसी कोशिका तक पहुँचने वाले पथों के रूप में निर्धारित कीजिए, dp[0][0] को 1 रखिए और ऊपर वाली कोशिका तथा बाईं ओर वाली कोशिका को जोड़िए। कोने में आपका उत्तर होता है। 🧭