# #Imagine we have a board divided into 4 rows and 5 columns. There are pebbles scattered across...

## Question:

#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))

**Related Book For**

## Microeconomics An Intuitive Approach with Calculus

ISBN: 978-0538453257

1st edition

Authors: Thomas Nechyba