โจทย์ทั้งหมด
ปานกลาง 0 ข้อที่แก้แล้ว อัตราผ่าน 0%

ผลรวมเส้นทางที่มากที่สุดในสามเหลี่ยม

หาผลรวมที่มากที่สุดบนเส้นทางจากยอดของสามเหลี่ยมตัวเลขลงไปจนถึงแถวล่างสุด

สิ่งที่คุณจะได้เรียนรู้

  • แทนการค้นหาแบบเอกซ์โพเนนเชียลด้วยกำหนดการพลวัต
  • รวมผลลัพธ์จากแถวด้านล่าง
  • จัดการค่าติดลบและอินพุตว่าง

โจทย์

สามเหลี่ยมตัวเลขมีค่าหนึ่งค่าในแถวที่ 0 สองค่าในแถวที่ 1 และเพิ่มขึ้นเช่นนี้ไปเรื่อย ๆ ให้เริ่มที่ยอดแล้วเดินลงทีละแถว โดยแต่ละครั้งเลือกไปที่ค่าที่อยู่ใต้ลงไปตรง ๆ หรือค่าที่อยู่ด้านล่างทางขวา (จากตำแหน่ง i ไปยัง i หรือ i + 1) ให้หาเส้นทางที่ผลรวมของค่ามากที่สุด การลองทุกเส้นทางทำให้งานเพิ่มเป็นสองเท่าในทุกแถว แต่ถ้าคำนวณย้อนขึ้นจากแถวล่างสุด งานจะเพิ่มขึ้นแบบกำลังสองเท่านั้น

จงเขียนฟังก์ชัน 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 กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน

คำตอบที่ผ่านดีที่สุดของแต่ละคน คำตอบที่เร็วกว่า ใช้หน่วยความจำน้อยกว่า และได้คะแนนดีกว่าจะอยู่ด้านบน

ยังไม่มีคำตอบที่ผ่าน แก้โจทย์นี้แล้วคว้าอันดับหนึ่งไปเลย

เรียนรู้จากคนอื่น

แนวทางจากชุมชน

ยังไม่มีวิธีทำที่เผยแพร่ ลองแก้โจทย์นี้เพื่อแชร์วิธีแรก