Gold Mine Problem | Python program to solve Gold Mine problem ; Returns maximum amount of gold that can be collected when journey started from first column and moves allowed are right , right - up and right - down ; Create a table for storing intermediate results and initialize all cells to 0. The first row of goldMineTable gives the maximum gold that the miner can collect when starts that row ; Gold collected on going to the cell on the right ( -> ) ; Gold collected on going to the cell to right up ( / ) ; Gold collected on going to the cell to right down ( \ ) ; Max gold collected from taking either of the above 3 paths ; The max amount of gold collected will be the max value in first column of all rows ; Driver code
MAX = 100 NEW_LINE def getMaxGold ( gold , m , n ) : NEW_LINE INDENT goldTable = [ [ 0 for i in range ( n ) ] for j in range ( m ) ] NEW_LINE for col in range ( n - 1 , - 1 , - 1 ) : NEW_LINE INDENT for row in range ( m ) : NEW_LINE INDENT if ( col == n - 1 ) : NEW_LINE INDENT right = 0 NEW_LINE DEDENT else : NEW_LINE INDENT right = goldTable [ row ] [ col + 1 ] NEW_LINE DEDENT if ( row == 0 or col == n - 1 ) : NEW_LINE INDENT right_up = 0 NEW_LINE DEDENT else : NEW_LINE INDENT right_up = goldTable [ row - 1 ] [ col + 1 ] NEW_LINE DEDENT if ( row == m - 1 or col == n - 1 ) : NEW_LINE INDENT right_down = 0 NEW_LINE DEDENT else : NEW_LINE INDENT right_down = goldTable [ row + 1 ] [ col + 1 ] NEW_LINE DEDENT goldTable [ row ] [ col ] = gold [ row ] [ col ] + max ( right , right_up , right_down ) NEW_LINE DEDENT DEDENT res = goldTable [ 0 ] [ 0 ] NEW_LINE for i in range ( 1 , m ) : NEW_LINE INDENT res = max ( res , goldTable [ i ] [ 0 ] ) NEW_LINE DEDENT return res NEW_LINE DEDENT gold = [ [ 1 , 3 , 1 , 5 ] , [ 2 , 2 , 4 , 1 ] , [ 5 , 0 , 2 , 3 ] , [ 0 , 6 , 1 , 2 ] ] NEW_LINE m = 4 NEW_LINE n = 4 NEW_LINE print ( getMaxGold ( gold , m , n ) ) NEW_LINE