Count possible ways to construct buildings | Returns count of possible ways for N sections ; Base case ; 2 for one side and 4 for two sides ; countB is count of ways with a building at the end countS is count of ways with a space at the end prev_countB and prev_countS are previous values of countB and countS respectively . Initialize countB and countS for one side ; Use the above recursive formula for calculating countB and countS using previous values ; Result for one side is sum of ways ending with building and ending with space ; Result for 2 sides is square of result for one side ; Driver program
def countWays ( N ) : NEW_LINE INDENT if ( N == 1 ) : NEW_LINE INDENT return 4 NEW_LINE DEDENT countB = 1 NEW_LINE countS = 1 NEW_LINE for i in range ( 2 , N + 1 ) : NEW_LINE INDENT prev_countB = countB NEW_LINE prev_countS = countS NEW_LINE countS = prev_countB + prev_countS NEW_LINE countB = prev_countS NEW_LINE DEDENT result = countS + countB NEW_LINE return ( result * result ) NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT N = 3 NEW_LINE print ( " Count ▁ of ▁ ways ▁ for ▁ " , N , " ▁ sections ▁ is ▁ " , countWays ( N ) ) NEW_LINE DEDENT