100% rate

6. You are in a rectangular maze organized in the form of M N cells/locations. You are starting at the upper left corner (grid location: (1,1)) and you want to go to the lower right corner (grid location: (M,N)). From any location, you can move either to the right or to the bottom, or go diagonal. Le, from (i, j) you can move to (i,j + 1) or (i+1,j) or to (i+1,j+1). Cost of moving right or down is 2, while the cost of moving diagonally is 3. The grid has several cells that contain diamonds of whose value lies between 1 and 10. L.e, if you land in such cells you earn an amount that is equal to the value of the diamond in the cell Your objective is to go from the start corner to the destination corner by picking up diamonds such that the difference between the sum of the value of diamonds you picked and sum of the costs incurred is maximized. Write a dynamic programming algorithm, based on appropriate recurrence relation. State the recurrence, algorithm and analyze its time complexity