Minimum change in lanes required to cross all barriers | Java program for the above approach ; Function to find the minimum number of changes of lane required ; If there is a barrier , then add very large value ; Add the minimum value to move forword with or without crossing barrier ; Return the minimum value of dp [ 0 ] , dp [ 1 ] and dp [ 2 ] ; Driver Code
class GFG { static int minChangeInLane ( int barrier [ ] , int n ) { int dp [ ] = { 1 , 0 , 1 } ; for ( int j = 0 ; j < n ; j ++ ) { int val = barrier [ j ] ; if ( val > 0 ) { dp [ val - 1 ] = ( int ) 1e6 ; } for ( int i = 0 ; i < 3 ; i ++ ) { if ( val != i + 1 ) { dp [ i ] = Math . min ( dp [ i ] , Math . min ( dp [ ( i + 1 ) % 3 ] , dp [ ( i + 2 ) % 3 ] ) + 1 ) ; } } } return Math . min ( dp [ 0 ] , Math . min ( dp [ 1 ] , dp [ 2 ] ) ) ; } public static void main ( String [ ] args ) { int barrier [ ] = { 0 , 1 , 2 , 3 , 0 } ; int N = barrier . length ; System . out . print ( minChangeInLane ( barrier , N ) ) ; } }