We define the complexity of an integer n to be the minimum number of operations we need to represent n using only the digits 0, 1, ..., 9 (multiple times each, if necessary).
The operations allowed are addition (+), subtraction (-), multiplication (*), integer division (/, defined as the floor of normal division), and modulo operator (%, defined as a % b = a - b * (a / b)).
Examples:
The complexity of 72 is 1. We can represent 72 using one operation as 8 * 9.
The complexity of 19 is 2. We need at least two operations to represent 19. One representation is 5 * 5 - 6.
The complexity of 7 is 0. We don't need any operations, since the number is already a digit.
The complexity of 4187 is 5. We need at least five operations to represent 4187. One representation is (5 * 9 + 8) * (8 * 9 + 7).
The complexity of 14771 is 6. We need at least six operations to represent 14771. One representation is 9 * 9 * 9 * 9 * 9 / 4 + 9
Given N, find the sum of complexities of all positive integers less than N.
1<=N<=17000
Example
For N = 100, the answer=155
For N = 417, the answer=1055
For N = 1000, the answer=3145
what I need to know is : the formula to find the answer or the process to solve the maths
It looks like the task on the dynamically programming with very big space. Rough upbound of the minimum number of operations is about 12 (17000 <9^6)