title: How many possible way for barcode to appear with limitation constrain
body: <p>This is one of homeworks from a grader I've got. I've been struggling on this question for two days now. The topic is about Dynamic programming and I have no idea how to make sense of it.</p>
  
  <p>The detail is the following.</p>
  
  <p>A barcode consists of black and white vertical lines in different arrangement. For simplicity, we use a string of “0” and “1” to identify a barcode such that “0” represents a black line while “1” represents a white line. </p>
  
  <p>A barcode is designed to be robust to error thus it has to follow some specific rules:</p>
  
  <p>1) A barcode must consists of exactly <strong>N</strong> lines</p>
  
  <p>2) There can be no more than <strong>M</strong> consecutive lines of same color. For example, when <strong>M=3</strong>, the barcode “01100001” is illegal because it consists of four consecutive white lines. However, 1001100 is legal.</p>
  
  <p>3) We define “color changing” as follows. Color changing occurs when two
  consecutive lines have different colors. For example, 1001100 has 3 color
  changing. A barcode must have exactly <strong>K</strong> color changing.</p>
  
  <p>4) The first line is always a black line.</p>
  
  <p>We interest in knowing the number of possible barcode with respect to given
  values of <strong>N</strong>, <strong>M</strong> and <strong>K</strong>.</p>
  
  <p><strong>Input</strong>
  There are only one line contains 3 integers N, M and K where 1 &lt;= N,M &lt;= 30 and 0 &lt;= K &lt;= 30</p>
  
  <p><strong>Output</strong>
  The output must contain exactly one line giving the number of possible barcodes.</p>
  
  <p><strong>For example</strong></p>
  
  <p><strong>Input</strong></p>
  
  <pre><code>4 3 1
  </code></pre>
  
  <p><strong>Output</strong></p>
  
  <pre><code>3
  </code></pre>
  
  <p><strong>Input</strong></p>
  
  <pre><code>5 2 2
  </code></pre>
  
  <p><strong>Output</strong></p>
  
  <pre><code>3
  </code></pre>
  
  <p><strong>Input</strong></p>
  
  <pre><code>7 9 4
  </code></pre>
  
  <p><strong>Output</strong></p>
  
  <pre><code>15
  </code></pre>