Red John is Back

This post is in reference to SPOJ 21525. Red John is Back PPBRJB.

You need to build a solid wall that’s 4-high and N-wide using 4×1 bricks. The question: how many distinct walls can you build?

If you place a brick vertically, that takes up one entire column. Placing 4 bricks horizontally takes up four. The solution makes use of the simple dynamic programming recursion shown below:

dp-bricks

Without further ado, my DP implementation is in git and below:

Leave a Reply

Your email address will not be published. Required fields are marked *