საშუალო

სამკუთხედის ჯამი

მოცემულია triangle (სამკუთხედის) ფორმის რიცხვების მატრიცა.

თქვენი დავალებაა დააბრუნოთ მინიმალური გზის (path) ჯამი ზემოდან ქვემოთ.

გაითვალისწინეთ, ყოველ ნაბიჯზე შეგიძლიათ გადახვიდეთ მხოლოდ მიმდინარე რიგის მეზობელ რიცხვზე ქვედა რიგში. უფრო კონკრეტულად, თუ თქვენ მიმდინარე რიგში ინდექს i ხართ, შეგიძლიათ გადახვიდეთ შემდეგი რიგის: i ან i+1 ან i-1 ინდექსებზე.

გადაცემული პარამეტრებიდან გამომდინარე ამოცანას აუცილებლად ექნება ერთი სწორი პასუხი.

პირველი მაგალითი

პარამეტრები: triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
შედეგი: 11
განმარტება: ამ მასივიდან ვღებულოთ ესეთ სამკუთხედს:

მინიმალური გზის ჯამი ზემოდან ქვემოთ არის 2 + 3 + 5 + 1 = 11.

მეორე მაგალითი

პარამეტრები: triangle = [[-10]]
შედეგი: -10

მესამე მაგალითი

პარამეტრები: triangle = [[1], [2, 3]]
შედეგი: 3

მეოთხე მაგალითი

პარამეტრები: triangle = [[5], [9, 6], [4, 6, 8], [0, 7, 1, 5], [4, 2, 3, 6, 9], [7, 1, 8, 3, 2, 4]]
შედეგი: 21

ამოცანის ამოხსნა შესაძლებელია ბევრი გზით, ცადეთ ისეთი ალგორითმის მოფიქრება, რომელიც O(n²)-თან ახლოს არის.