Given two positive integer N and M. The task is to find the number of arrays of size N that can be formed such that:
1. Each element is in the range [1, M].
2. All adjacent element are such that one of them divide the another i.e element A_{i} divides A_{i + 1 }or A_{i+1} divides A_{i}.
Example 1:
Input: 
N = 3
M = 3
Output : 
17
Explanation:
{1,1,1}, {1,1,2}, {1,1,3}, {1,2,1}, 
{1,2,2}, {1,3,1}, {1,3,3}, {2,1,1},
{2,1,2}, {2,1,3}, {2,2,1}, {2,2,2},
{3,1,1}, {3,1,2}, {3,1,3}, {3,3,1}, 
{3,3,3} are possible arrays.
Example 2:
Input: 
N = 1
M = 10 
Output: 
10
Explanation: 
{1}, {2}, {3}, {4}, {5}, 
{6}, {7}, {8}, {9}, {10}
are possible arrays.
Your Task:
You don't need to read input or print anything. Your task is to complete the function count() which take integers N and M as input parameter and returns the total the number of arrays of size N that can be formed with given constraints. The return value may long so take modulo 10^{9}+7. 
Expected Time Complexity: O(N*M*Log M) 
Expected Space Complexity: O(N*M) 
Constraints:
1<=N,M<=100

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Number theory

Dynamic programming

Starter code: #User function Template for python3

class Solution:
    def count(self,N, M):
        # code here

Solutions:
MAX = 1001

class Solution:

	def count(self, n, m):
		dp = [[0 for i in range(MAX)] for j in range(MAX)]
		di = [[] for i in range(MAX)]
		mu = [[] for i in range(MAX)]
		for i in range(1, m + 1):
			for j in range(2 * i, m + 1, i):
				di[j].append(i)
				mu[i].append(j)
			di[i].append(i)
		for i in range(1, m + 1):
			dp[1][i] = 1
		for i in range(2, n + 1):
			for j in range(1, m + 1):
				dp[i][j] = 0
				for x in di[j]:
					dp[i][j] += dp[i - 1][x]
				for x in mu[j]:
					dp[i][j] += dp[i - 1][x]
		ans = 0
		for i in range(1, m + 1):
			ans += dp[n][i]
			di[i].clear()
			mu[i].clear()
		mod = int(1000000000.0 + 7)
		return ans % mod


from collections import defaultdict

class Solution:

	def count(self, N, M):
		d = defaultdict(set)
		for i in range(1, M + 1):
			j = 1
			while j * j <= M:
				if i % j == 0:
					d[i].add(j)
					d[j].add(i)
				j += 1
			j = i
			while j <= M:
				d[i].add(j)
				d[j].add(i)
				j += i
		memo = {}

		def recur(i, prev):
			nonlocal N, M, memo, d
			if i >= N:
				return 0
			if i == N - 1:
				return 1
			if (i, prev) in memo:
				return memo[i, prev]
			res = 0
			for adj in d[prev]:
				res += recur(i + 1, adj)
			memo[i, prev] = res % (1000000000.0 + 7)
			return res
		res = 0
		for ele in d:
			res += recur(0, ele) % (1000000000.0 + 7)
		return int(res % (1000000000.0 + 7))


class Solution:

	def count(self, N, M):
		dp = [[0 for i in range(M + 5)] for i in range(0, N + 5)]
		for i in range(1, M + 1):
			dp[1][i] = 1
		MOD = 10 ** 9 + 7
		for i in range(2, N + 2):
			for j in range(1, M + 1):
				for k in range(j, M + 1, j):
					dp[i][k] = (dp[i][k] + dp[i - 1][j]) % MOD
					if j == k:
						continue
					dp[i][j] = (dp[i][j] + dp[i - 1][k]) % MOD
		ans = 0
		for i in range(1, M + 1):
			ans = (ans + dp[N][i]) % MOD
		return ans


class Solution:

	def count(self, N, M):
		arr = [i + 1 for i in range(M)]
		dp = [set() for i in range(M + 1)]
		for i in range(1, M):
			for j in range(i + 1, M + 1):
				if j % i == 0 or i % j == 0:
					dp[i].add(j)
					dp[j].add(i)
		mod = 10 ** 9 + 7
		dic = {}

		def dfs(m, n):
			if (m, n) in dic:
				return dic[m, n]
			if n == 0:
				return 1
			c = 0
			for i in dp[m]:
				c += dfs(i, n - 1) % mod
			c += dfs(m, n - 1) % mod
			dic[m, n] = c % mod
			return c % mod
		return dfs(1, N) % mod


from math import *

class Solution:

	def count(self, n, m):
		arr = [1]
		MAX = 1000
		MOD = 1000000007
		dp = [[0 for i in range(MAX)] for j in range(MAX)]
		di = [[] for i in range(MAX)]
		mu = [[] for i in range(MAX)]
		for i in range(1, m + 1):
			for j in range(2 * i, m + 1, i):
				di[j].append(i)
				mu[i].append(j)
			di[i].append(i)
		for i in range(1, m + 1):
			dp[1][i] = 1
		for i in range(2, n + 1):
			for j in range(1, m + 1):
				dp[i][j] = 0
				for x in di[j]:
					dp[i][j] = (dp[i][j] % MOD + dp[i - 1][x] % MOD) % MOD
				for x in mu[j]:
					dp[i][j] = (dp[i][j] % MOD + dp[i - 1][x] % MOD) % MOD
		ans = 0
		for i in range(1, m + 1):
			ans = (ans % MOD + dp[n][i] % MOD) % MOD
		return ans