Count of N size Arrays with each element as multiple or divisor of its neighbours

Given two numbers N and K, the task is to count the number of all possible arrays of size N such that each element is a positive integer less than or equal to K and is either a multiple or a divisor of its neighbours. Since the answer can be large, print it modulo 10⁹ + 7.

Examples: 

Input: N = 2, K = 3
Output: 7
Explanation: All the possible arrays are – { {1, 2}, {2, 1}, {1, 3}, {3, 1}, {1, 1}, {2, 2}, {3, 3} }

Input: N = 5, K = 4
Output: 380

Naive Approach: The simplest approach is to find all combinations of arrays of size N where each element is less than or equal to ‘K’, and for each combination check if adjacent elements are multiples of each other or not. 

Time Complexity: O(K^N * N)
Auxiliary Space: O(N)

Efficient Approach: The above approach can also be optimized by using Dynamic Programming because of its overlapping subproblems and optimal substructure property using the following observation: 

The subproblems can be stored in dp[][] table using memoization where dp[i][prev] stores the count of all possible arrays from the i^th position till the end, with prev as the value in (i-t)th index. 

Follow the steps below to solve the problem:

• Initialize a global multidimensional array dp[][] to store the result of each recursive call.
• Find the multiples and divisors of all numbers from 1 to K and store them.
• Define a recursive function and perform the following operations:
  • If the value of i is N, return 1 as a valid array has been formed.
  • If the result of the state dp[i][prev] is already computed, return that calculated value.
  • Iterate through all the multiples and divisors of ‘prev‘, and for each number call the recursive function for (i + 1)th index.
• The value at dp[0][1] will be the required answer.

Below is the implementation of the above approach : 

Time Complexity: O(N * K * √K)
Auxiliary Space: O(N * K)