The optimal algorithm choice depends on the context (such as the relative cost of the multiplication and the number of times a given exponent is re-used).
[2] The problem of finding the shortest addition chain cannot be solved by dynamic programming, because it does not satisfy the assumption of optimal substructure.
For example, in the shortest addition chain for a15 above, the subproblem for a6 must be computed as (a3)2 since a3 is re-used (as opposed to, say, a6 = a2(a2)2, which also requires three multiplies).
However, the slowness of division compared to multiplication makes this technique unattractive in general.
For exponentiation to negative integer powers, on the other hand, since one division is required anyway, an addition-subtraction chain is often beneficial.