Count ways to build street under given constraints | Java program to 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 program for checking above function
public class GFG { static long countWays ( int n ) { long dp [ ] [ ] = new long [ 2 ] [ n + 1 ] ; dp [ 0 ] [ 1 ] = 1 ; dp [ 1 ] [ 1 ] = 2 ; for ( int 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 ] ; } public static void main ( String [ ] args ) { int n = 5 ; System . out . print ( " Total ▁ no ▁ of ▁ ways ▁ with ▁ n ▁ = ▁ " + n + " ▁ are : ▁ " + countWays ( n ) ) ; } }