Edit: I am hoping to get some review / make sure I am understanding dynamic programming correctly.
I am trying to print out all additive numbers up to digits n using dynamic programming. Additive numbers are those like 123, 1235, etc., where the sum of every 2 digits from left to right is equal to the third digit. In this definition, non-trivial additive numbers must necessarily be at least 3 digits long, though for numbers of 2 digits or less one could trivially print out all digits 0-99. Furthermore, this definition implies the set of additive numbers is finite and relatively tiny.
If there is a better definition of an additive number or I have misunderstood it, feel free to point out.
I believe dynamic programming is a good approach to this problem, because the solutions of n - 1 need to be re-used to compute the solutions to n. A brute force algorithm is possible, but I think far more inefficient.
Here is my solution in Python. It will print them all out and also return the trellis that contains the solutions for each digit. Note that for n >= 9, there are no more additive numbers.
# -*- coding: utf-8 -*-
"""Dynamic programming
"""
BASE_CASE = 3
def print_additive_numbers(n=BASE_CASE):
"""Prints all additive numbers up to n digits
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.
We use dynamic programming to iteratively generate
additive numbers for increasing digits, as the solutions to
n = 3 are re-used for n = 4, n = 5, etc.
Args:
n: the maximum number of digits for each representation
Returns:
A dictionary mapping each number of digits to all
possible additive numbers.
"""
if n < BASE_CASE:
raise ValueError, "additive numbers always have 3 or more digits"
#build the initial trellis
trellis = {}
trellis[BASE_CASE] = {}
for i in xrange(1, 9):
row = []
for j in xrange(0, 9):
if i + j <= 9:
print str(i) + str(j) + str(i + j)
row.append(str(j) + str(i + j))
trellis[BASE_CASE][i] = row
for m in xrange(BASE_CASE + 1, n + 1):
trellis[m] = {}
for key in trellis[m - 1].keys():
row = []
for digits in trellis[m - 1][key]:
first_digit = int(digits[-2])
second_digit = int(digits[-1])
new_digit = first_digit + second_digit
if new_digit <= 9:
row.append(digits + str(new_digit))
print str(key) + digits + str(new_digit)
trellis[m][key] = row
return trellis
t = print_additive_numbers(9)