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
def countWays ( n ) : NEW_LINE INDENT dp = [ [ 0 ] * ( n + 1 ) for i in range ( 2 ) ] NEW_LINE dp [ 0 ] [ 1 ] = 1 NEW_LINE dp [ 1 ] [ 1 ] = 2 NEW_LINE for i in range ( 2 , n + 1 ) : NEW_LINE INDENT dp [ 0 ] [ i ] = dp [ 0 ] [ i - 1 ] + dp [ 1 ] [ i - 1 ] NEW_LINE dp [ 1 ] [ i ] = ( dp [ 0 ] [ i - 1 ] * 2 + dp [ 1 ] [ i - 1 ] ) NEW_LINE DEDENT return dp [ 0 ] [ n ] + dp [ 1 ] [ n ] NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT n = 5 NEW_LINE print ( " Total ▁ no ▁ of ▁ ways ▁ with ▁ n ▁ = " , n , " are : " , countWays ( n ) ) NEW_LINE DEDENT