The minimum cost path is: $4->3->4->2->1->4->4->2,$ with a total cost of

$24.$ Notice that a greedy solution will not work!

a$)(10$ points$)$ Write a recursive algorithm to solve this problem. Clearly define your

recurrence relation. Your solution should have a time complexity of O$(2$m$+$n$).$

b$)(10$ points$)$ Write a dynamic programming algorithm to solve this problem using

bottom$-$up dynamic programming. Your solution should have a time complexity of

O$($m $\backslash$times n$).$

c$)(10$ points$)$ Justify the runtime complexity for both your recursive and dynamic

programming solutions.