Solving addition chain problems using dynamic programming

Question

You are given a positive integer A. The goal is to construct the shortest possible sequence of integers ending with A, using the following rules:

1. The first element of the sequence is 1
2. Each of the successive elements is the sum of any two preceding elements (adding a single element to itself is also permissible)
3. Each element is larger than all the preceding elements; that is, the sequence is increasing.

For example, for A = 42, a possible solution is:

[1, 2, 3, 6, 12, 24, 30, 42]

Another possible solution for A = 42 is:

[1, 2, 4, 5, 8, 16, 21, 42]

After reading the problem statement, the first thing that came to my mind is dynamic programming (DP), hence I expressed it as a search problem and tried to write a recursive solution.

The search space up to A = 8 is:

                1
                |
                2
               / \
              /   \            
             3     4
            /|\   /|\
           / | \ 5 6 8
          /  |  \
         4   5   6
       /| |\  
      5 6 7 8

We can see that 4 occurs in two places, but in both cases the children of 4 are different. In one case the prior sequence is [1, 2, 4]. In the other case the prior sequence is [1, 2, 3, 4]. Therefore, we cannot say that we have overlapping sub-problems. Is there any way to apply DP to the above problem? Or I am wrong in judging that it can be solve using DP?

Answer 1

This is an addition chain...

http://en.wikipedia.org/wiki/Addition_chain

There is no known algorithm which can calculate a minimal addition chain for a given number with any guarantees of reasonable timing or small memory usage. However, several techniques to calculate relatively short chains exist. One very well known technique to calculate relatively short addition chains is the binary method, similar to exponentiation by squaring. Other well-known methods are the factor method and window method.

See also: New Methods For Generating Short Addition Chains in IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences.