Dynamic Programming for printing additive numbers up to digits n
1. Review


I like that you've written a docstring, but it is not quite correct. It claims that the function returns:

A dictionary mapping each number of digits to all
possible additive numbers.


but when I run it I get a more complicated data structure:

&gt;&gt;&gt; from pprint import pprint
&gt;&gt;&gt; pprint(additive_numbers(3))
{3: {1: ['01', '12', '23', '34', '45', '56', '67', '78', '89'],
     2: ['02', '13', '24', '35', '46', '57', '68', '79'],
     3: ['03', '14', '25', '36', '47', '58', '69'],
     4: ['04', '15', '26', '37', '48', '59'],
     5: ['05', '16', '27', '38', '49'],
     6: ['06', '17', '28', '39'],
     7: ['07', '18', '29'],
     8: ['08', '19']}}


Either the docstring or the result should be changed so that they match.
The code is not portable to Python 3 due to the use of the raise and print statements and the xrange function. It would be easy to make it portable, using range instead of xrange, the print function instead of the statement, and the modern form of raise:

raise ValueError("additive numbers always have 3 or more digits")

The function print_additive_numbers does three things: (i) it computes the numbers, (ii) it prints them, and (iii) it returns an internal data structure used in the computation. It's generally good practice for a function to have a single purpose, and then compose or combine functions to make a program. So I would redesign the function so that it does task (i); we can call print on the result if we need (ii). I don't think (iii) is necessary at all.
The code stores the last two digits of each additive number in the trellis structure in the form of a string. But this means that when it gets the digits out again it has to call int. This conversion back and forth is wasteful: it would be better to store the tuple (j, i + j) instead of the string str(j) + str(i + j).
The initial loop looks like this:

for i in xrange(1, 9):


but Python ranges are exclusive at the top, so this never generates the digit 9 and thus fails to find the additive numbers 909 and 9099. The initial loop needs to say range(1, 10).
The initial two loops look like this after correcting the problems noted above:

trellis[BASE_CASE] = {}
for i in range(1, 10):
    row = []
    for j in range(0, 10):
        if i + j &lt;= 9:
            row.append((j, i + j))
    trellis[BASE_CASE][i] = row


but the if could be omitted if we changed the bounds on j, like this:

trellis[BASE_CASE] = {}
for i in range(1, 10):
    row = []
    for j in range(10 - i):
        row.append((j, i + j))
    trellis[BASE_CASE][i] = row


or, using a list comprehension:

trellis[BASE_CASE] = {}
for i in range(1, 10):
    trellis[BASE_CASE][i] = [(j, i + j) for j in range(10 - i)]



2. A better algorithm

This is a problem for which dynamic programming is unnecessary! That's because dynamic programming is a technique that you use when you have to consult the answers to multiple overlapping subproblems in order to answer the current problem. But when generating additive numbers, there isn't really a problem to solve. Once you've chosen the first two digits, all the other digits follow without any choice.

So I would implement it like this:

def additive_numbers(n):
    """Generate additive numbers up to n digits, in numerical order.

    Additive numbers are numbers of the form 123, 1235, etc. where the
    sum of every 2 digits is equal to the third digit in the digit
    expansion of the number.

    &gt;&gt;&gt; list(additive_numbers(3))
    ... # doctest: +NORMALIZE_WHITESPACE
    [101, 112, 123, 134, 145, 156, 167, 178, 189, 202, 213, 224, 235,
     246, 257, 268, 279, 303, 314, 325, 336, 347, 358, 369, 404, 415,
     426, 437, 448, 459, 505, 516, 527, 538, 549, 606, 617, 628, 639,
     707, 718, 729, 808, 819, 909]

    The longest additive number is 8 digits long:

    &gt;&gt;&gt; list(additive_numbers(8)) == list(additive_numbers(9))
    True
    &gt;&gt;&gt; max(additive_numbers(8))
    10112358

    """
    for digits in range(3, n + 1):
        # Choose the first two digits.
        for i in range(1, 10):
            for j in range(10 - i):
                # m is the number generated so far, z is its last
                # digit, and y the penultimate digit.
                m, y, z = i * 10 + j, i, j
                for _ in range(digits - 2):
                    y, z = z, y + z
                    if z &gt; 9:
                        break
                    m = m * 10 + z
                else:
                    yield m


The examples in the docstring can be executed using the doctest module.