title: Lego Blocks - Dynamic Programming
body: <p>I'm trying to solve following DP problem:</p>
  
  <blockquote>
    <p>You have 4 types of lego blocks, of sizes 1 * 1 * 1, 1 * 1 * 2, 1 * 1
    * 3 and 1 * 1 * 4. Assume you have infinite number of blocks of each type.</p>
    
    <p>You want to make a wall of height H and width M out of these blocks.
    The wall should not have any holes in it. The wall you build should be
    one solid structure. A solid structure means that it should not be
    possible to separate the wall along any vertical line without cutting
    any lego block used to build the wall. The blocks can only be placed
    horizontally. In how many ways can the wall be built?</p>
  </blockquote>
  
  <p>Here is how I'm attempting it:
  Representing 1 * 1 * 1, 1 * 1 * 2, 1 * 1 * 3 and 1 * 1 * 4 blocks with a b c d
  . Valid patterns are indicated in bold. Invalid patterns are which can be broken by vertical line.</p>
  
  <blockquote>
    <p>H=1 &amp; W=3 #valid pattern=1<br> aa ab ba <strong>c</strong><br></p>
    
    <p>H=2 &amp; W=3 #valid pattern=9<br> 
    <img src="https://i.stack.imgur.com/U1UdX.png" alt="enter image description here"></p>
  </blockquote>
  
  <p>I'm trying to find recurrence pattern either to extend this by height or width.i.e to find values for H=3 &amp; W=3 or H=2&amp;W=4.</p>
  
  <p>Any inputs on how to formula-ize growth for this by height or weight?<br>
  P.S. The wall be always H*W*1.</p>