Count ways to build street under given constraints | Function to count ways of building a street of n rows ; Base case ; Ways of building houses in both the spots of ith row ; Ways of building an office in one of the two spots of ith row ; Total ways for n rows ; Driver code
function countWays ( n ) { let dp = new Array ( 2 ) ; for ( let i = 0 ; i < 2 ; i ++ ) { dp [ i ] = new Array ( n + 1 ) ; } dp [ 0 ] [ 1 ] = 1 ; dp [ 1 ] [ 1 ] = 2 ; for ( let i = 2 ; i <= n ; i ++ ) { dp [ 0 ] [ i ] = dp [ 0 ] [ i - 1 ] + dp [ 1 ] [ i - 1 ] ; dp [ 1 ] [ i ] = dp [ 0 ] [ i - 1 ] * 2 + dp [ 1 ] [ i - 1 ] ; } return dp [ 0 ] [ n ] + dp [ 1 ] [ n ] ; } let n = 5 ; document . write ( " " + n + " " + countWays ( n ) ) ;