Подсчитайте возможные массивы длины L, состоящие из первых N натуральных чисел и каждого элемента, делящего следующий элемент

Даны два положительных целых числа N и L , задача состоит в том, чтобы найти количество массивов длины L , состоящих из первых N натуральных чисел, таких, что каждый элемент массива делит следующий элемент.

Примеры:

Input: N = 3, L = 3
Output: 7
Explanation:
Following arrays has elements from the range [1, 3] and each array element divides its next element:

1. {1, 1, 1}
2. {1, 1, 2}
3. {1, 2, 2}
4. {1, 1, 3}
5. {1, 3, 3}
6. {2, 2, 2}
7. {3, 3, 3}

Therefore, the count of arrays is 7.

Input: N = 2, L = 4
Output: 5

Подход: Данную проблему можно решить с помощью динамического программирования и идеи решета Эратосфена. Выполните следующие шаги, чтобы решить проблему:

• Инициализируйте 2D-массив dp[][] , где dp[i][j] обозначает количество последовательностей длины i , которые заканчиваются на j , и инициализируйте dp[0][1] как 1 .
• Итерация по диапазону [0, L – 1] с использованием переменной i и вложенная итерация по диапазону [1, N] с использованием переменной j :
  • Так как следующий элемент построенного массива должен быть кратен текущему элементу, поэтому перебираем диапазон [j, N] с шагом j и обновляем значение dp[i + 1][k] до значения dp[ i][j] + dp[i + 1][k] .
• Инициализируйте переменную, скажем, ответьте как 0 , которая хранит результирующее количество массивов.
• Переберите диапазон [1, N] и добавьте значение dp[L][i] к переменной ans .
• После выполнения вышеуказанных шагов выведите в качестве результата значение ans .

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N*L*log N)
Вспомогательное пространство: O(N*L)