## Dynamic Programming (a tough one)

Post here if you don't find any other place for your post. But please, stay on-topic: algorithms, programming or something related to this web site and its services.

Moderator: Board moderators

The^Guard
New poster
Posts: 6
Joined: Wed Nov 23, 2005 11:16 pm

### Dynamic Programming (a tough one)

How many numbers with N digits are there (N is even, N<1000), so that the sum of the first N/2 digits equals the product of the last N/2 digits.

Example:

Input
2

Output
9

Explanation: 11, 22, 33, 44, 55, 66, 77, 88, 99
-------------------
Input
4

Output
207
--------------------------------------------------------

Now, I know that I should use dynamic programming to solve this one, but I don't know how. Please help!
Amir Aavani
New poster
Posts: 30
Joined: Wed Oct 23, 2002 6:53 am
Let T(n,s) be the number of cases in which sum of n numbers (all less than 10) are eqaul to S.
It is not hard to find a recursive descripton for T(n+ 1,s).
Let T(n,s) be the number of cases in which sum of n numbers (all less than 10) are eqaul to S and the first number is non-zero.
T'(n,s) can be expressed by T(n+ 1,s).
The answer of your question "How many numbers with 2N digits are there so that the sum of the first N digits equals the product of the last" is

sum of T(n,s)* T'(n,s) over s in range of [1..9n].

It is clear that you must find T(n,s) by a dynamic method.
The^Guard
New poster
Posts: 6
Joined: Wed Nov 23, 2005 11:16 pm

### Pleaseeee....

Can you give me a more datailed explanation, please? I'm really not that good at dynamic programming. Possibly, if you have time, a small code.

Thanks!