Build a Wall From Bricks | Dynamic Programming Set 4

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)

  • Rahul Garg

    Nice explaination.

Site Footer