5) (50 points) Arrange numbers in an equilateral triangle with n numbers at the base, like the one shown below for n 4. The problem is to find the smallest sum in a descent from the triangle's apex to its base through a sequence of adjacent numbers 2 5 4 3 8 6 6 (Note that 4 in the second row has two adjacent numbers in the third row: 3 and 7, but not 1.) Thus, for the triangle above the minimal sum is 2 5+16-14. Store the elements of the triangle in an array A[i,jl, indexed top-to-bottom by rows i -1 umnsj 1,, i. ., and left- to-right by col b) What is the relationship between adjacent elements of the triangle in terms of i and j? In the example above, the item 4-A[2 2] is adjacent to the items 3-A[3, 2] and 7 = A3, 3] below it. Write your answer in the form "Al. /| is adjacent to elements AL J and AL J below, foris-. c) Solve this problem using dynamic programming by writing down its recurrence equation. Hint: the initial conditions are S[n, = A[n, for j = 1, , n and the final result is to return S[1, 1 ]. Explain how to solve this problem by the greedy method. Hint: connect the numbers to form a weighted graph and use an algorithm we already covered in class. d) e) Is the greedy approach more efficient than the dynamic programming solution? Explain