Gold Mine Problem | Java 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
import java . util . Arrays ; class GFG { static final int MAX = 100 ; static int getMaxGold ( int gold [ ] [ ] , int m , int n ) { int goldTable [ ] [ ] = new int [ m ] [ n ] ; for ( int [ ] rows : goldTable ) Arrays . fill ( rows , 0 ) ; for ( int col = n - 1 ; col >= 0 ; col -- ) { for ( int row = 0 ; row < m ; row ++ ) { int right = ( col == n - 1 ) ? 0 : goldTable [ row ] [ col + 1 ] ; int right_up = ( row == 0 col == n - 1 ) ? 0 : goldTable [ row - 1 ] [ col + 1 ] ; int right_down = ( row == m - 1 col == n - 1 ) ? 0 : goldTable [ row + 1 ] [ col + 1 ] ; goldTable [ row ] [ col ] = gold [ row ] [ col ] + Math . max ( right , Math . max ( right_up , right_down ) ) ; } } int res = goldTable [ 0 ] [ 0 ] ; for ( int i = 1 ; i < m ; i ++ ) res = Math . max ( res , goldTable [ i ] [ 0 ] ) ; return res ; } public static void main ( String arg [ ] ) { int gold [ ] [ ] = { { 1 , 3 , 1 , 5 } , { 2 , 2 , 4 , 1 } , { 5 , 0 , 2 , 3 } , { 0 , 6 , 1 , 2 } } ; int m = 4 , n = 4 ; System . out . print ( getMaxGold ( gold , m , n ) ) ; } }