Find minimum steps required to reach the end of a matrix | Set 2 | Javascript implementation of the approach ; 2d array to store states of dp ; Array to determine whether a state has been solved before ; Function to return the minimum steps required ; Base cases ; If a state has been solved before it won 't be evaluated again ; Recurrence relation ; Driver code
let n = 3 ; let dp = new Array ( n ) ; let v = new Array ( n ) ; for ( let i = 0 ; i < n ; i ++ ) { dp [ i ] = new Array ( n ) ; v [ i ] = new Array ( n ) ; for ( let j = 0 ; j < n ; j ++ ) { dp [ i ] [ j ] = 0 ; v [ i ] [ j ] = 0 ; } } function minSteps ( i , j , arr ) { if ( i == n - 1 && j == n - 1 ) { return 0 ; } if ( i > n - 1 j > n - 1 ) { return 9999999 ; } if ( v [ i ] [ j ] == 1 ) { return dp [ i ] [ j ] ; } v [ i ] [ j ] = 1 ; dp [ i ] [ j ] = 9999999 ; for ( let k = Math . max ( 0 , arr [ i ] [ j ] + j - n + 1 ) ; k <= Math . min ( n - i - 1 , arr [ i ] [ j ] ) ; k ++ ) { dp [ i ] [ j ] = Math . min ( dp [ i ] [ j ] , minSteps ( i + k , j + arr [ i ] [ j ] - k , arr ) ) ; } dp [ i ] [ j ] ++ ; return dp [ i ] [ j ] ; } let arr = [ [ 4 , 1 , 2 ] , [ 1 , 1 , 1 ] , [ 2 , 1 , 1 ] ] ; let ans = minSteps ( 0 , 0 , arr ) ; if ( ans >= 9999999 ) { document . write ( - 1 ) ; } else { document . write ( ans ) ; }