OJ Board

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!

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.

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!