There is a neat way to solve this problem using graph theory.
First of all you need to decide the states and their transitions.
3 ->[3,6,9] and so on.
Imagine each state to be a vertex in a graph and each transition to be a directed edge.
Now construct the adjacency matrix.
In your case it may look like:-
Note that over here the
1s represent that you can transition from the current state to that state.
Thus, if the
5th element of the
3rd row is
1 it means that you can go from
Finding all permissible combinations of length
n is equivalent to finding all the walks of length
n in this graph.
(Adjacency_Matrix)^n results in a matrix of the same dimension where (i,j) denotes number of unique walks of length
n between vertex i and j.
Since first element cannot be
0, you can sum up the values of this matrix for all
i!=0. This would be your answer.
Matrix Exponentiation takes O(d^3 log(n)) time. d-> DImension of matrix(10).
The DP approach would take too much time for n>10^4. Since this approach is
log(n) it will perform better for large values of n.