Find the number of arrangements for all 0<=j<=i-1 matchsticks, you can use these to find the number of arrangements for the first ‘i’ matchsticks, store these values in an array A[], your answer will be A[N]. Suppose that you want to find the answer for position ‘i’, we will go through all the possibilities for the rightmost digit in the arrangement, and then we will count the number of ways in which we can do that. Let’s suppose that you decide that the last digit will be ‘8’, so you will be needing 7 matchsticks for it, and your answer in that case will be A[i-7].
This is because all different arrangements of the first i-7 numbers, followed by the digit ‘8’ that you’re forming with the last 7 matchsticks will give you new arrangements. So, in this way, you will sum up the new arrangements for all possible digits. So, for any ‘i’, your answer will be given by:
A[i]=A[i-6]+A[i-2]+A[i-5]+A[i-5]+A[i-4]+A[i-5]+A[i-3]+A[i-7]+A[i-5], each term in this summation represents a different choice for the rightmost digit in the number that you will be forming. The complexity of this solution is O(N), and I think it can be improved if you use matrix exponentiation. Let me know (comment) if anything isn’t clear.
