title: Dynamic programming table for number of steps problem
body: <p>There is a well known problem called "Triple Step" that states:</p>
  
  <p><em>"A child is running up a staircase with n steps and can hop either 1 step, 2 steps, or 3 steps at a time. Implement a method to count how many possible ways the child can run up the stairs"</em></p>
  
  <p>The algorithm below is a version without memoization:</p>
  
  <pre><code>int countWays(int n) {
      if (n &lt; 0) {
          return 0;
      } else if (n == 0) {
          return 1;
      } else {
          return countWays(n-1) + countWays(n-2) + countWays(n-3);
      }
  }
  </code></pre>
  
  <p>I know that its runtime can be improved from the exponential time complexity. 
  But I really would like to know how to build a dynamic programming table over this problem,
  for example I tried the table below for n being 4 steps:</p>
  
  <pre><code>   0 | 1 | 2 | 3 | 4 &lt;= staircase size
  1  1 | 1 | 1 | 1 | 1
  2  1 | 1 | 2 | 2 | 3
  3  1 | 1 | 2 | 3 | 4 &lt;=** There's something wrong because for n=4 the output should be 7
  </code></pre>
  
  <p>Could someone give me a hint about how this table could be built for the problem above? (or maybe the table is fine and I'm not able to interpret it right)</p>
  
  <p>Thanks!</p>