text: Minimum change in lanes required to cross all barriers | C ++ 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
code: #include <bits/stdc++.h> NEW_LINE using namespace std ; 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 ] = 1e6 ; } for ( int i = 0 ; i < 3 ; i ++ ) { if ( val != i + 1 ) { dp [ i ] = min ( dp [ i ] , min ( dp [ ( i + 1 ) % 3 ] , dp [ ( i + 2 ) % 3 ] ) + 1 ) ; } } } return min ( dp [ 0 ] , min ( dp [ 1 ] , dp [ 2 ] ) ) ; } int main ( ) { int barrier [ ] = { 0 , 1 , 2 , 3 , 0 } ; int N = sizeof ( barrier ) / sizeof ( barrier [ 0 ] ) ; cout << minChangeInLane ( barrier , N ) ; return 0 ; }