you are given an n $\backslash$times n grid containing integer values $($representing the obstacle at that

location$).$ You need to find a cheapest route from the top left corner, or index $(1,1),$ to the

bottom right corner, or index $($n$,$n$)$ that at each step moves one spot down, right or down$-$right

diagonally. Such a route is just a sequence of pairs such as $(1,1)$ to $(2,2)$ to $(2,3)$ etc. Give an O$($n

$2$

$)$

dynamic programming algorithm to solve this problem. The figure below shows one such problem and

the correct path to take $($the path has a score of $14).$ Note, in some instances there may be multiple

such paths, but you only need to find one.