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