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 rigth ( -> ) ; 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
< ? php function getMaxGold ( $ gold , $ m , $ n ) { $ MAX = 100 ; $ goldTable = array ( array ( ) ) ; for ( $ i = 0 ; $ i < $ m ; $ i ++ ) for ( $ j = 0 ; $ j < $ n ; $ j ++ ) $ goldTable [ $ i ] [ $ j ] = 0 ; for ( $ col = $ n - 1 ; $ col >= 0 ; $ col -- ) { for ( $ row = 0 ; $ row < $ m ; $ row ++ ) { if ( $ col == $ n - 1 ) $ right = 0 ; else $ right = $ goldTable [ $ row ] [ $ col + 1 ] ; if ( $ row == 0 or $ col == $ n - 1 ) $ right_up = 0 ; else $ right_up = $ goldTable [ $ row - 1 ] [ $ col + 1 ] ; if ( $ row == $ m - 1 or $ col == $ n - 1 ) $ right_down = 0 ; else $ right_down = $ goldTable [ $ row + 1 ] [ $ col + 1 ] ; $ goldTable [ $ row ] [ $ col ] = $ gold [ $ row ] [ $ col ] + max ( $ right , $ right_up , $ right_down ) ; } } $ res = $ goldTable [ 0 ] [ 0 ] ; for ( $ i = 0 ; $ i < $ m ; $ i ++ ) $ res = max ( $ res , $ goldTable [ $ i ] [ 0 ] ) ; return $ res ; } $ gold = array ( array ( 1 , 3 , 1 , 5 ) , array ( 2 , 2 , 4 , 1 ) , array ( 5 , 0 , 2 , 3 ) , array ( 0 , 6 , 1 , 2 ) ) ; $ m = 4 ; $ n = 4 ; echo getMaxGold ( $ gold , $ m , $ n ) ; ? >