# Depend of N dimension Arrays with every component as a number of or divisor of its neighbours Given two numbers N and Okay, the duty is to depend the variety of all doable arrays of dimension N such that every component is a optimistic integer lower than or equal to Okay and is both a a number of or a divisor of its neighbours. For the reason that reply will be massive, print it modulo 109 + 7.

Examples:

Enter: N = 2, Okay = 3
Output: 7
Rationalization: All of the doable arrays are – { {1, 2}, {2, 1}, {1, 3}, {3, 1}, {1, 1}, {2, 2}, {3, 3} }

Enter: N = 5, Okay = 4
Output: 380

Naive Strategy: The best strategy is to search out all mixtures of arrays of dimension N the place every component is lower than or equal to ‘Okay’, and for every mixture verify if adjoining parts are multiples of one another or not.

Time Complexity: O(OkayN * N)
Auxiliary Area: O(N)

Environment friendly Strategy: The above strategy can be optimized through the use of Dynamic Programming due to its overlapping subproblems and optimum substructure property utilizing the next remark:

The subproblems will be saved in dp[][] desk utilizing memoization the place dp[i][prev] shops the depend of all doable arrays from the ith place until the tip, with prev as the worth in (i-t)th index.

Comply with the steps under to unravel the issue:

• Initialize a worldwide multidimensional array dp[][] to retailer the results of every recursive name.
• Discover the multiples and divisors of all numbers from 1 to Okay and retailer them.
• Outline a recursive perform and carry out the next operations:
• If the worth of i is N, return 1 as a sound array has been fashioned.
• If the results of the state dp[i][prev] is already computed, return that calculated worth.
• Iterate by means of all of the multiples and divisors of ‘prev‘, and for every quantity name the recursive perform for (i + 1)th index.
• The worth at dp would be the required reply.

Under is the implementation of the above strategy :

## C++

 `#embrace ` `utilizing` `namespace` `std;` ` `  `int` `dp;` ` `  `vector > data(1005);` ` `  `int` `countOfArrays(``int` `index, ``int` `prev, ``int` `N)` `{` `    ` `    ` `    ``if` `(index == N) {` `        ``return` `1;` `    ``}` ` `  `    ` `    ``if` `(dp[index][prev] != -1) {` `        ``return` `dp[index][prev];` `    ``}` `    ``dp[index][prev] = 0;` ` `  `    ` `    ` `    ``for` `(``auto` `num : data[prev]) {` ` `  `        ` `        ` `        ``dp[index][prev]` `            ``+= countOfArrays(index + 1,` `                             ``num, N);` ` `  `        ` `        ``dp[index][prev] %= 1000000007;` `    ``}` ` `  `    ` `    ``return` `dp[index][prev];` `}` ` `  `int` `UtilCountOfArrays(``int` `N, ``int` `Okay)` `{` ` `  `    ` `    ``memset``(dp, -1, ``sizeof` `dp);` ` `  `    ` `    ` `    ``for` `(``int` `i = 1; i <= Okay; ++i) {` `        ``for` `(``int` `j = 1; j <= Okay; ++j) {` `            ``if` `(i % j == 0 or j % i == 0) {` `                ``data[i].push_back(j);` `            ``}` `        ``}` `    ``}` ` `  `    ` `    ``return` `countOfArrays(0, 1, N);` `}` ` `  `int` `principal()` `{` `    ` `    ``int` `N = 2;` `    ``int` `Okay = 3;` `    ``cout << UtilCountOfArrays(N, Okay) << endl;` `    ``return` `0;` `}`

Time Complexity: O(N * Okay * √Okay)
Auxiliary Area: O(N * Okay)