Minimum cells required to reach destination with jumps equal to cell values | function to count minimum cells required to be covered to reach destination ; to store min cells required to be covered to reach a particular cell ; initially no cells can be reached ; base case ; building up the dp [ ] [ ] matrix ; dp [ i ] [ j ] != INT_MAX denotes that cell ( i , j ) can be reached from cell ( 0 , 0 ) and the other half of the condition finds the cell on the right that can be reached from ( i , j ) ; the other half of the condition finds the cell right below that can be reached from ( i , j ) ; it true then cell ( m - 1 , n - 1 ) can be reached from cell ( 0 , 0 ) and returns the minimum number of cells covered ; cell ( m - 1 , n - 1 ) cannot be reached from cell ( 0 , 0 ) ; Driver Code
< ? php function minCells ( $ mat , $ m , $ n ) { $ dp = array ( array ( ) ) ; for ( $ i = 0 ; $ i < $ m ; $ i ++ ) for ( $ j = 0 ; $ j < $ n ; $ j ++ ) $ dp [ $ i ] [ $ j ] = PHP_INT_MAX ; $ dp [ 0 ] [ 0 ] = 1 ; for ( $ i = 0 ; $ i < $ m ; $ i ++ ) { for ( $ j = 0 ; $ j < $ n ; $ j ++ ) { if ( $ dp [ $ i ] [ $ j ] != PHP_INT_MAX and ( $ j + $ mat [ $ i ] [ $ j ] ) < $ n and ( $ dp [ $ i ] [ $ j ] + 1 ) < $ dp [ $ i ] [ $ j + $ mat [ $ i ] [ $ j ] ] ) $ dp [ $ i ] [ $ j + $ mat [ $ i ] [ $ j ] ] = $ dp [ $ i ] [ $ j ] + 1 ; if ( $ dp [ $ i ] [ $ j ] != PHP_INT_MAX and ( $ i + $ mat [ $ i ] [ $ j ] ) < $ m and ( $ dp [ $ i ] [ $ j ] + 1 ) < $ dp [ $ i + $ mat [ $ i ] [ $ j ] ] [ $ j ] ) $ dp [ $ i + $ mat [ $ i ] [ $ j ] ] [ $ j ] = $ dp [ $ i ] [ $ j ] + 1 ; } } if ( $ dp [ $ m - 1 ] [ $ n - 1 ] != PHP_INT_MAX ) return $ dp [ $ m - 1 ] [ $ n - 1 ] ; return -1 ; } $ mat = array ( array ( 2 , 3 , 2 , 1 , 4 ) , array ( 3 , 2 , 5 , 8 , 2 ) , array ( 1 , 1 , 2 , 2 , 1 ) ) ; $ m = 3 ; $ n = 5 ; echo " Minimum ▁ number ▁ of ▁ cells ▁ = ▁ " , minCells ( $ mat , $ m , $ n ) ; ? >