a) Integers are written on each unit square of a square of size n x n, where n is given positive integers. Every time we are in the square, we make as much money as the number in this square (or lose money if the number in the square is negative.) We can go either one square to the right or one square down with each step. Our goal is to earn the most money from the upper left corner to the lower right corner. For the given number n and the given n x n dimensional matrix A, write an algorithm designed with dynamic programming method that achieves our goal. b) Describe your algorithm on the example below.

4	-5	15	7
2	1	9	-2
-8	3	4	6
20	-6	3	2

c) Can a greedy approach be used to solve this problem? If yes, prove it. If your answer is no, show an example.

d) Write the pseudo code of your algorithm.

Please answer it in 100 minutes.