Problem 1: 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 traffic lights, each of which has some delay associated with it. Let dij represent the delay caused by the intersection at position (i,j) of the grid. At each intersection, you can turn in the direction of the intersecting road, or continue on the current road. Design a dynamic pro- gramming 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 small- est total delay. Assume you don't need to deal with delays at your starting or ending point. Hint: Define T[i, j] to be the minimum total delay required to get to the (i, j) intersection from the starting position. What subproblems do you need in order to calculate this value Problem 1: 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 traffic lights, each of which has some delay associated with it. Let dij represent the delay caused by the intersection at position (i,j) of the grid. At each intersection, you can turn in the direction of the intersecting road, or continue on the current road. Design a dynamic pro- gramming 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 small- est total delay. Assume you don't need to deal with delays at your starting or ending point. Hint: Define T[i, j] to be the minimum total delay required to get to the (i, j) intersection from the starting position. What subproblems do you need in order to calculate this value