Suppose you are trying to navigate a set of roads to get from point A to point B. Assume that the roads are on a grid. All roads are one-way roads, and point either straight north or straight east. Your job is to get from the southwest corner to the northeast corner of the grid. At each intersection, there are trac lights, each of which has some delay associated with it. Let di;j represent the delay caused by the intersection at position (i; j) of the grid. At each intersection, you can go north or go east. Note: when calculating the total delay, include the delays associated with the rst (southwest) and last (northeast) intersections on your route.

Design a dynamic programming algorithm to determine the path of roads you should take to get from the southwest corner to the northeast corner of the grid with the smallest total delay. (Hint: if you want to get to location (i; j), where could you have been immediately before?) If you want to draw a DAG and explain your solution in terms of it, you can, but you can use other solutions if you prefer.