0
$\begingroup$

Given two integers $n$ and $m$, how many numbers exist such that all integers have all digits from $0$ to $n-1$, the difference between two adjacent digits is exactly $1$, and the number of digits in the integer is at most $m$?

The integer cannot start with a $0$. All digits from $0$ to $n-1$ must be present.

Example: for $n = 3$ and $m = 6$ there are $18$ such numbers ($210, 2101, 21012, 210121 \ldots$)

I know there is a dynamic programming method to solve this. After looking the solution, I am not able to understand it. Can anybody please give any good solution to me?

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ You should present the solution you have at hand and describe your specific problems -- then we can really help you. $\endgroup$
    – Raphael
    Commented Aug 29, 2013 at 13:28
  • $\begingroup$ I had the recursion at my hand. But I could not figure out the parameters and what the table was calculating and how. This is something like this: f(S, d, l) = f(S|1<<d+1, d+1, l+1) + f(S|<<d-1, d-1, l+1). But, now, everything is clear from Yuval's answer. $\endgroup$
    – Rahul Sharma
    Commented Aug 29, 2013 at 15:50
  • $\begingroup$ Good thing it matches, then; without insider knowledge Yuval may be talking about a whole other recurrence. That is to say, please include such detail in future questions you post. $\endgroup$
    – Raphael
    Commented Aug 30, 2013 at 11:05

1 Answer 1

Reset to default
0
$\begingroup$

Hint: The table consists of cells $T(S,d,\ell)$, which count numbers of length $\ell$ in which the last digit is $d$ and the set of digits is $S$. Unfortunately this solution is exponential in $n$.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.