# Count the number of integers satisfying two conditions using DP

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?

• You should present the solution you have at hand and describe your specific problems -- then we can really help you. – Raphael Aug 29 '13 at 13:28
• 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. – Rahul Sharma Aug 29 '13 at 15:50
• 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. – Raphael Aug 30 '13 at 11:05

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$.