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
< ? php function countWays ( $ n ) { $ dp [ 0 ] [ 1 ] = 1 ; $ dp [ 1 ] [ 1 ] = 2 ; for ( $ 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 ] ; } $ n = 5 ; echo " Total ▁ no ▁ of ▁ ways ▁ with ▁ n ▁ = ▁ " , $ n , " ▁ are : ▁ " , countWays ( $ n ) , " STRNEWLINE " ; ? >