Count ways to generate N digit number such that its every digit divisible by previous digit

Given a number N, the task is to count the number of ways to create an N digit number from digits 1 to 9 such that every digit is divisible by its previous digit that is if the number is represented by an array of digits A then A[i + 1] % A[i] == 0. print the answer modulo 10⁹ + 7.

Examples:

Input: N = 2
Output: 23
Explanation: For N = 2 possible answers are 11, 12, 13, 14, 15, 16, 17, 18, 19, 22, 24, 26, 28, 33, 36, 39, 44, 48, 55, 66, 77, 88, and 99.

Input: N = 3
Output: 44

Naive approach: The basic way to solve the problem is as follows:

The basic way to solve this problem is to generate all possible combinations by using a recursive approach.

Time Complexity: O(9^N)
Auxiliary Space: O(1)

Efficient Approach: The above approach can be optimized based on the following idea:

Dynamic programming can be used to solve this problem

dp[i][j] represents the number of ways of creating a number of size i and j is its previous digit taken.

It can be observed that the recursive function is called exponential times. That means that some states are called repeatedly.

So the idea is to store the value of each state. This can be done by storing the value of a state and whenever the function is called, returning the stored value without computing again.

Follow the steps below to solve the problem:

Create a recursive function that takes two parameters representing i^th position to be filled and j representing the last digit taken.
Call the recursive function for choosing all digits from 1 to 9.
Base case if all positions filled return 1.
Create a 2d array of dp[N][10] initially filled with -1.
If the answer for a particular state is computed then save it in dp[i][j].
If the answer for a particular state is already computed then just return dp[i][j].