Problem $5.($Worth $3$ points$)$

We are standing on the bottom left corner of a human$-$sized $nn$ chessboard. Each square has

some number of goats standing on it$.$ We wish to travel the board until we get to the top right

corner, where at each step we can either move one square to the right or one square up$.$ Each

time we get to a square, we give a carrot to each of the goats on it$.$ Describe a dynamic

programming algorithm that finds a path that maximizes the number of goats that receive a

carrot. The running time should be $O(n^2).$