JavaScript (ES6),  111 ... 84  80 bytes

Returns true rather than $1$ for $n=2$.

f=(n,j)=>(g=(i,x,e=1)=>i?e>n?g(i-1,x):g(i-1,x+e)+g(i,x,e*x):x==n)(j,2)||f(n,-~j)

Try it online!

Commented

f = (                     // f is the main recursive function taking:

  n,                      //   n = input

  j                       //   j = maximum number of steps

) => (                    //

  g = (                   // g is another recursive function taking:

    i,                    //   i = number of remaining steps

    x,                    //   x = current sum

    e = 1                 //   e = current exponentiated part

  ) =>                    //

    i ?                   // if there's still at least one step to go:

      e > n ?             //   if e is greater than n:

                          //     add the result of a recursive call with:

        g(i - 1, x)       //       i - 1, x unchanged and e = 1

      :                   //   else:

                          //     add the sum of recursive calls with:

        g(i - 1, x + e) + //       i - 1, x + e and e = 1

        g(i, x, e * x)    //       i unchanged, x unchanged and e = e * x

    :                     // else:

      x == n              //   stop recursion; return 1 if x = n

)(j, 2)                   // initial call to g with i = j and x = 2

|| f(n, -~j)              // if it fails, try again with j + 1

05AB1E, 17 bytes

2¸[˜DIå#εIÝmy+]I¢

Try it online!

Haskell, 78 75 bytes

This implementation uses a breath-first-search in the "tree" of iteratively all necessary mappings x -> x + x^j.

j#x=x+x^j

f n=[sum[1|x<-l,x==n]|l<-iterate((#)<$>[0..n]<*>)[2],n`elem`l]!!0

Try it online!

Explanation

-- computes the mapping x -> x + x^j

j#x=x+x^j                          

--iteratively apply this function for all exponents [0,1,...,n] (for all previous values, starting with the only value [2])

                            iterate((#)<$>[0..n]<*>)[2] 

-- find each iteration where our target number occurs

    [                   |l<-...........................,n`elem`l] 

-- find how many times it occurs

     sum   [1|x<-l,x==n] 

-- pick the first entry

f n=.............................................................!!0

Python 2, 72 bytes

f=lambda n,l=[2]:l.count(n)or f(n,[x+x**j for x in l for j in range(n)])

Try it online!

Perl 5 (-lp), 79 bytes

$e=$_;@,=(2);@,=map{$x=$_;map$x+$x**$_,0..log($e)/log$x}@,until$_=grep$_==$e,@,

TIO

CJam (27 bytes)

qi2a{{_W$,f#f+~2}%_W$&!}ge=

Online demo

Warning: this gets very memory-intensive very fast.

Dissection:

qi            e# Read input and parse to int n (accessed from the bottom of the stack as W$)

2a            e# Start with [2]

{             e# Loop

  {           e#   Map each integer x in the current list

    _W$,f#f+~ e#     to x+x^i for 0 <= i < n

    2         e#   and add a bonus 2 for the special case

  }%          e#   Gather these in the new list

  _W$&!       e#   Until the list contains an n

}g

e=            e# Count occurrences

The bonus 2s (to handle the special case of input 2, because while loops are more expensive than do-while loops) mean that the size of the list grows very fast, and the use of exponents up to n-1 means that the values of the larger numbers in the list grow very fast.

Jelly, 16 bytes

2+*¥þ³Ḷ¤F$n³Ạ$¿ċ

Try it online!

A full program taking as its argument $n$ and returning the number of ways to reach $n$ using the minimal path length. Inefficient for larger $n$.

Haskell, 65 bytes

([2]%)

l%n|elem n l=sum[1|x<-l,x==n]|1>0=[x+x^k|x<-l,k<-[0..n]]%n

Try it online!

Golfing flawr's breadth-first-search. I also tried going backwards from n, but it was longer:

73 bytes

q.pure

q l|elem 2l=sum[1|2<-l]|1>0=q[x|n<-l,x<-[0..n],i<-[0..n],x+x^i==n]

Try it online!

Pyth, 24 bytes

VQIJ/mu+G^GHd2^U.lQ2NQJB

Try it online!

This should produce the correct output, but is very slow (the 372 test case times out on TIO). I could make it shorter by replacing .lQ2 with Q, but this would make the runtime horrendous.

Note: Produces no output for unreachable numbers $(n leq 1)$

Explanation

VQ                        # for N in range(Q (=input)):

   J                      #   J =

     m                    #     map(lambda d:

      u                   #       reduce(lambda G,H:

       +G^GH              #         G + G^H,

            d2            #         d (list), 2 (starting value) ),

              ^U.lQ2N     #       cartesian_product(range(log(Q, 2)), N)

    /                Q    #     .count(Q)

  IJ                  JB  #   if J: print(J); break