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!
Dynamic Programming (a tough one)
Moderator: Board moderators

 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 nonzero.
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.
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 nonzero.
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.
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!
Thanks!