Given a value N , if we want to build a wall of size 4xN and we have an infinite supply of bricks of size **1×4** and **4×1** , In How many way we can build that wall using bricks?

**For Example** for N=4 ,

Wall size become 4×4 ,

There are two ways to build wall of size 4×4 = {4 bricks of size 1×4 placed vertically, 4 bricks of size 4×1 placed horizontally}

i.e answer is 2

1) Optimal Substructure

To count the total number of ways we can divide all set solution in two ways

- Solution that contain 4×1 brick
- Solution that contain 1×4 brick

Let Wall[n] contain the total number of ways to build a wall of size 4xN from 4×1 and 1×4 brick.

then Wall[n] can be written as **Wall[n-1] + Wall[n-4]**

i.e Wall[n] = Wall[n-1] + Wall[n-4]

- When we include brick of 4×1 dimension then we need to solve for only
**n-1** - When we include brick of 1×4 dimension then we have to place four bricks of same dimension , So we have to solve for
**n-4**

So Recurrence relation become **Wall[n] = Wall[n-1] + Wall[n-4]**

2) Overlapping Sub-problems

Let take n = 4

Wall[5] / \ Wall[4] Wall[1] / \ | Wall[3] Wall[0] Wall[0]

As we can see **Wall[0]** is solving twice so this problem has overlapping subproblem property.

Since this problem has both **Optimal Substructure** and **Overlapping SubProblem** property So this problem has both properties of **Dynamic Programming**.

Recomputing of same subProblem can be avoided by taking temporary array Wall[n] and build this array in a bottom up manner.

#include<iostream> #include<vector> using namespace std; //We will construct this array in bottom up manner int Wall[41] = {0}; int CountNoOfWalls(int n) { if(n<0) return 0; //Base Case: For i = 0,1,2,3 , Wall[i] = 1 for(int i=0 ; i<4;i++) { Wall[i] = 1; } if(n<4) { return Wall[n]; } //Fill rest of array in bottom up manner for(int i=4 ; i<=n;i++) { /* Total count of solution = Solution that contain brick 4x1 size * Solution that contain brick 1x4 size */ Wall[i] = Wall[i-1] + Wall[i-4]; } return Wall[n]; } int main() { int t; int n; cin>>n; //Find Total number of ways to build wall of size 4xN cout<<CountNoOfWalls(n); }

Time Complexity : O(n)