Algorithms questions.

Thanks

Let A be an integer array with n columns and n rows. The array encodes the map of a room of size n n. We have A[j] = 1 if there is a gold coin at location (i,j) in the room, and otherwise A[i,j] - 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. The running time of vour algorithm should be polynomial in T2 Hint: Use dynamic programming Let A be an integer array with n columns and n rows. The array encodes the map of a room of size n n. We have A[j] = 1 if there is a gold coin at location (i,j) in the room, and otherwise A[i,j] - 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. The running time of vour algorithm should be polynomial in T2 Hint: Use dynamic programming