How to memoize recursive path of length n search

I'm not sure what you're memoizing (perhaps you could explain it in words?) but there seem to be overlapping sub-problems here. If I understand correctly, except for "A", any specific instance of a letter can only be reached from a neighbouring previous letter in the alphabet. That means we can store the number of paths from each specific instance of a letter. When that specific instance is reached on subsequent occasions, we can avoid recursing into it.

Depth first search:

 d1 d2 d3 d4
   c1   c2
      b
    a1 a2

 .....f(c1) = f(d1) + f(d2) = 2
 .....f(c2) = f(d3) + f(d4) = 2
 ...f(b) = f(c1) + f(c2) = 4
 f(a1) = f(b) = 4
 f(a2) = f(b) = 4