सभी चुनौतियाँ
मध्यम 0 हल किए गए 0% स्वीकृति

त्रिभुज में अधिकतम पथ योग

संख्या-त्रिभुज के शीर्ष से नीचे की पंक्ति तक जाने वाले पथ का सबसे बड़ा योग खोजिए।

आप क्या सीखेंगे

  • Exponential खोज की जगह dynamic programming इस्तेमाल करना
  • नीचे वाली पंक्ति के परिणामों को जोड़कर इस्तेमाल करना
  • ऋणात्मक मान और खाली इनपुट संभालना

समस्या

संख्या-त्रिभुज में पंक्ति 0 पर एक मान होता है, पंक्ति 1 पर दो, और इसी तरह आगे। सबसे ऊपर से शुरू कीजिए और हर बार एक पंक्ति नीचे जाइए, या तो ठीक नीचे वाले मान पर या उसके दाएँ वाले मान पर (स्थान i से i या i + 1 पर)। वह पथ खोजिए जिसके मानों का योग सबसे ज़्यादा हो। हर पथ आज़माने पर हर पंक्ति के साथ काम दोगुना हो जाता है; नीचे की पंक्ति से ऊपर की ओर हल करने पर समय quadratic ही रहता है।

triangle_max_path_sum(triangle) लिखिए।

इनपुट

triangle: ऊपर से नीचे तक की पंक्तियाँ; पंक्ति r में r + 1 मान हैं, जो ऋणात्मक भी हो सकते हैं।

आउटपुट

ऊपर से नीचे तक जाने वाले किसी पथ का सबसे बड़ा संभव योग लौटाइए। खाली त्रिभुज के लिए 0 लौटाइए।

सीमाएँ

0 ≤ पंक्तियाँ ≤ 100; −1000 ≤ मान ≤ 1000

उदाहरण

उदाहरण 1
इनपुट:
triangle = [
    [4],
    [7, 2],
    [1, 9, 5],
    [6, 3, 8, 2]
]

अपेक्षित आउटपुट:
expected = 28
इनपुट:
std::vector<std::vector<long long>> triangle = {
    {4},
    {7, 2},
    {1, 9, 5},
    {6, 3, 8, 2}
};

अपेक्षित आउटपुट:
long long expected = 28;
इनपुट:
long[][] triangle = new long[][] {
    new long[] {4},
    new long[] {7, 2},
    new long[] {1, 9, 5},
    new long[] {6, 3, 8, 2}
};

अपेक्षित आउटपुट:
long expected = 28;

व्याख्या

सबसे अच्छा पथ 4, 7, 9, 8 है (स्थान 0, 0, 1, 2), जिसका योग 28 है।

उदाहरण 2
इनपुट:
triangle = [
    [-3],
    [5, -8],
    [-1, 2, 9]
]

अपेक्षित आउटपुट:
expected = 4
इनपुट:
std::vector<std::vector<long long>> triangle = {
    {-3},
    {5, -8},
    {-1, 2, 9}
};

अपेक्षित आउटपुट:
long long expected = 4;
इनपुट:
long[][] triangle = new long[][] {
    new long[] {-3},
    new long[] {5, -8},
    new long[] {-1, 2, 9}
};

अपेक्षित आउटपुट:
long expected = 4;

व्याख्या

ऋणात्मक मानों के साथ −3, 5, 2 से 4 मिलता है जबकि −3, −8, 9 से −2, इसलिए उत्तर 4 है।

कैसे हल करें

पहले खुद कोशिश करें, फिर एक-एक करके संकेत खोलें।

संकेत 1

नीचे की पंक्ति से शुरू कीजिए: नीचे के किसी खाने से सबसे अच्छा पथ बस उसका अपना मान है।

संकेत 2

किसी खाने से सबसे अच्छा पथ उसका मान है, जिसमें नीचे के दो खानों के सबसे अच्छे पथों में से बड़ा वाला जोड़ा जाता है।

संकेत 3

हर पंक्ति को ऊपर की ओर हल कर लेने के बाद, सबसे ऊपर वाले खाने में उत्तर होता है।

अपेक्षित जटिलता

समय O(rows²), अतिरिक्त स्थान O(rows)

संदर्भ

यह चुनौती CodeUtility के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।

हर कोडर का सबसे अच्छा पास हुआ समाधान। तेज़, कम मेमोरी वाले और बेहतर रेटिंग वाले समाधान ऊपर रहते हैं।

अभी कोई पास हुआ समाधान नहीं है। इसे हल करें और पहला स्थान पाएँ।

दूसरों से सीखें

समुदाय समाधान

अभी तक कोई प्रकाशित समाधान नहीं। पहला साझा करने के लिए इस चुनौती को हल करें।