Shortest Addition Chain

Haskell, 57 bytes

c=[1]:[x++[a+b]|x<-c,a<-x,b<-x]
f n=[x|x<-c,last x==n]!!0

A brute force solution. Try it online!

Explanation

The infinite list c contains all addition chains, ordered by length. It is defined inductively in terms of itself, by taking a list x from c and two elements from x, and appending their sum to x. The function f finds the first list in c that ends with the desired number.

c=            -- c is the list of lists
 [1]:         -- containing [1] and
 [x           -- each list x
  ++[a+b]     -- extended with a+b
 |x<-c,       -- where x is drawn from c,
  a<-x,       -- a is drawn from x and
  b<-x]       -- b is drawn from x.
f n=          -- f on input n is:
 [x           -- take list of those lists x
 |x<-c,       -- where x is drawn from c and
  last x==n]  -- x ends with n,
 !!0          -- return its first element.

Brachylog, 14 bytes

∧≜;1{j⊇Ċ+}ᵃ⁽?∋

Try it online!

A brute-force submission that builds all possible addition chains using iterative deepening, stopping when a chain containing its right argument is found. Unlike most Brachylog submissions, this is a function submission that inputs via its right argument (conventionally called the Output) and outputs via its left argument (conventionally called the Input); doing this is somewhat controversial, but the highest-voted meta answer on the subject says it's legal (and doing so is consistent with our normal I/O defaults for functions). If we used the input and output in a more conventional way, this would be 16 bytes (∧≜;1{j⊇Ċ+}ᵃ⁽.∋?∧), because the right-hand side of the program would not be able to make use of the implicit constraint (thus would need that disabled, and a new explicit constraint given, at a cost of 2 bytes).

Explanation

∧≜;1{j⊇Ċ+}ᵃ⁽?∋
∧               Disable implicit constraint to read the left argument
 ≜;        ⁽    Evaluation order hint: minimize number of iterations
    {    }ᵃ     Repeatedly run the following:
   1      ᵃ       From {1 on the first iteration, results seen so far otherwise}
     j            Make {two} copies of each list element
      ⊇           Find a subset of the elements
       Ċ          which has size 2
        +         and which sums to {the new result for the next iteration}
             ∋    If the list of results seen so far contains {the right argument}
            ?     Output it via the left argument {then terminate}

An interesting subtlety here is what happens on the first iteration, where the input is a number rather than a list like on the other iterations; we start with the number 1, make two copies of every digit (making the number 11), then find a 2-digit subsequence of it (also the number 11). Then we take its digit sum, which is 2, and as such the sequence starts [1,2] like we want. On future iterations, we're starting with a list like [1,2], doubling it to [1,2,1,2], then taking a two-element subsequence ([1,1], [1,2], [2,1], or [2,2]); clearly, the sums of each of these will be valid next elements of the addition chain.

It's a little frustrating here that the evaluation order hint is needed here, especially the ≜ component (it appears that ᵃ takes its evaluation order hint from inside rather than outside by default, thus the rather crude use of ≜ in order to force the issue).

PHP, 195 Bytes

function p($a){global$argn,$r;if(!$r||$a<$r)if(end($a)==$argn)$r=$a;else foreach($a as$x)foreach($a as$y)in_array($w=$x+$y,$a)||$w>$argn||$w<=max($a)?:p(array_merge($a,[$w]));}p([1]);print_r($r);

Try it online!