Problem $2.$ Dynamic Programming $(10$ points$)$

You are given a triangle of non$-$negative numbers with i numbers at row $i.$ You want to find the

maximum path sum starting at the top of the triangle and moving to any of the numbers on the

bottom row. At each step you can go to any of the $($up to$)$ two neighboring numbers in the row

below.

$3$

$74$

$246$

$8593$

$($b$)$ Give a recursive equation OPT$(i,j)$ that would compute the value of the maximum path for

row $i$ up through position $j.$

Solution:

$($c$)$ Give complete pseudocode for a dynamic$-$programming solution to this algorithm and give a

bound on its run$-$time.

Solution: