समस्या
संख्या-त्रिभुज में पंक्ति 0 पर एक मान होता है, पंक्ति 1 पर दो, और इसी तरह आगे। सबसे ऊपर से शुरू कीजिए और हर बार एक पंक्ति नीचे जाइए, या तो ठीक नीचे वाले मान पर या उसके दाएँ वाले मान पर (स्थान i से i या i + 1 पर)। वह पथ खोजिए जिसके मानों का योग सबसे ज़्यादा हो। हर पथ आज़माने पर हर पंक्ति के साथ काम दोगुना हो जाता है; नीचे की पंक्ति से ऊपर की ओर हल करने पर समय quadratic ही रहता है।
triangle_max_path_sum(triangle) लिखिए।
इनपुट
triangle: ऊपर से नीचे तक की पंक्तियाँ; पंक्ति r में r + 1 मान हैं, जो ऋणात्मक भी हो सकते हैं।
आउटपुट
ऊपर से नीचे तक जाने वाले किसी पथ का सबसे बड़ा संभव योग लौटाइए। खाली त्रिभुज के लिए 0 लौटाइए।
सीमाएँ
0 ≤ पंक्तियाँ ≤ 100; −1000 ≤ मान ≤ 1000
उदाहरण
इनपुट:
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 है।
इनपुट:
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 के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।