Problem 2: Indiana Jones and the temple of doom. Let A be an integer array with n columns and n rows. The array encodes the map of a room of size nxn. We have Ai,j] = 1 if there is a gold coin at location (ij) in the room, and otherwise Ali, il = 0. Indiana Jones is initially located at position (1, 1), which is the north-west corner of the room, and has to reach the exit at location (n,n), which is the south-east corner. Indiana Jones is in a hurry, so he can move only south, or east. That is, at each step, starting at location (i, j) he can either move to location (i+1, j), or i, j +1). Note that he cannot move diagonally. Design an algorithm which, given the array A as input, outputs a sequence of moves for Indiana Jones, that allows him to collect the maximum possible number of gold coins before leaving the room. Prove that your algorithm is correct and that it runs in polynomial time. Hint: Use dynamic programming