title: Number of Paths in a Triangle
body: <p>I recently encountered a much more difficult variation of this problem, but realized I couldn't generate a solution for this very simple case. I searched Stack Overflow but couldn't find a resource that previously answered this.</p>
  
  <p>You are given a triangle ABC, and you must compute the number of paths of certain length that start at and end at 'A'. Say our function f(3) is called, it must return the number of paths of length 3 that start and end at A: 2 (ABA,ACA).</p>
  
  <p>I'm having trouble formulating an elegant solution. Right now, I've written a solution that generates all possible paths, but for larger lengths, the program is just too slow. I know there must be a nice dynamic programming solution that reuses sequences that we've previously computed but I can't quite figure it out. All help greatly appreciated.</p>
  
  <p>My dumb code:</p>
  
  <pre><code>def paths(n,sequence):
      t = ['A','B','C']
      if len(sequence) &lt; n:
          for node in set(t) - set(sequence[-1]):
              paths(n,sequence+node)
      else:
          if sequence[0] == 'A' and sequence[-1] == 'A':
              print sequence
  </code></pre>