Project Euler Problem 164
Statement
How many 20 digit numbers n (without any leading zero) exist such that no three consecutive digits of n have a sum greater than 9?
Solution
Typical DP problem, the base cases are when length is 1, and the possibilities is 10 minus the sum of the last 2 digits.
from itertools import product d = {} for i in range(0, 10): for j in range(0, 10): d[(1, i, j)] = 10 - i def solve(*args): if args in d: return d[args] l, sum_last, last_dig = args result = 0 for i in range(0, 10 - sum_last): result += solve(l - 1, last_dig + i, i) d[args] = result return result if __name__ == '__main__': result = 0 for t in filter(lambda x: x[0] < 10, map(lambda t: (sum(t), t[1]), product(range(1, 10), range(0, 10)) ) ): tmp = solve(18, *t) result += tmp print("The result is:", result)
The Python file is available for download here.