Problem $1(20$ points$)$

Consider a robot moving down on an $nn$ grid. Its goal is to move to the

bottom of the grid while consuming as little fuel as possible. At each step it can

select from one of three possible actions: move straight down or move diagonally

left or right. If the robot ever steps off the left or right side of the grid it reappears

in the appropriate location on the other side.

In each square of the grid, there is a different amount of fuel. Here is an

example grid with a sequence of decisions $($with a total fuel cost of $5).$

Develop a dynamic programming algorithm the robot can use to solve this

problem. Provide a description of the algorithm in plain English, pseudocode,

and a runtime analysis.

The input is an $nn$ grid of numbers. The output is the total fuel usage$-$you

do not need to return the path.