You are playing a game on an n n grid of cells. Each cell contains a single integer: the cell in row r, column c contains the integer A[r][c], where A[1..n][1..n] is a two-dimensional array of integers. You start at the top-left cell (1, 1) and will move to the bottom-right cell (n, n). At each step, you can only move to the cell immediately below or to the right. Specifically, from cell (r, c) you can move to (r + 1, c) or (r, c + 1) only. Your score is equal to the sum of the integers among all cells you have passed through: you would like to maximise this score.

a.[10 marks] Give an O(n 2 ) algorithm that computes the maximum possible score.

b.[5 marks] Describe how to extend your algorithm from part (a) to also output any path that produces this maximum possible score. This path should be output as a series of D (down) and R moves, for instance DDRDRR is a valid path on a 44 grid. The overall time complexity of the algorithm should still be O(n 2 ).

c.[5 marks] Suppose as input you are given the array A[1..n][1..n] in readonly memory. This means that you can freely read its values, but cannot modify it in any way. Design an algorithm that runs in O(n 2 ) time that outputs any path with maximum possible score, just as in part (b). However, your algorithm may only use O(n ? n) additional memory on top of the input array. This additional memory can be freely read from or written to.