#Imagine we have a board divided into 4 rows and 5 columns. There are pebbles scattered across the board, one per (row, columm) spot
#Pebbles exist at locations:  (0,0), (0,1), (1,1), (1,2),(1,3), (2,0), (2,3), (2,4), (3,0)
#There is a robot that starts at (0,0). It can move to the right or down.
#What is the max number of pebbles the robot can collect, if it traverses a legal path to (3,4)?

#Below is the recursive solution. Change this code to use memoization to optimize this code (or update your own solution):

 Defined functions BEGIN

# diagnostic print tool
def print_matrix(mat,m,n) :
r = 0
while(r < m) :
 c = 0
 while(c < n) :
  print(mat[r][c], end=" ")
  c = c + 1
 print()
 r = r + 1
print()

def f(r,c , board) :
if(r < 0 or c < 0) :
 return 0
a = f(r,c-1 , board)
b = f(r-1,c , board)
max = a
if(b > a) :
 max = b
return board[r][c] + max

Defined functions END

# Making a (m x n) 2-D list called board
m = 4
n = 5
board = []
r = 0
while(r < m) :
temp = []
c = 0
while(c < n) :
 temp.append(0)
 c = c + 1
board.append(temp)
r = r + 1

print_matrix(board,m,n)

# populate board with some pebbles
board[0][0] = 1
board[0][1] = 1
board[1][1] = 1
board[1][2] = 1
board[1][3] = 1
board[2][0] = 1
board[2][3] = 1
board[2][4] = 1
board[3][0] = 1
print_matrix(board,m,n)

# call f
r = 3
c = 4
print("r =",r)
print("c =",c)
print("Answer = ",f(r,c, board))