Подсчет последовательности длины K в диапазоне [1, N], где каждый элемент кратен предыдущему

Даны два целых числа N и K. Задача состоит в том, чтобы найти количество последовательностей из K элементов из диапазона [1, N], где каждый элемент кратен предыдущему элементу.

Пример:

Input: N = 4, K = 3 
Output: 13
Explanation: The sequences that can be made from the integers 1, 2, 3, 4 having 3 elements are: {1, 1, 1}, {2, 2, 2}, {3, 3, 3}, {4, 4, 4}, {1, 1, 2}, {1, 2, 2}, {1, 2, 4}, {1, 1, 3}, {1, 3, 3}, {1, 1, 4}, {1, 4, 4}, {2, 2, 4}, and {2, 4, 4}.

Input: N = 9, K = 5 
Output: 111

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

• Создайте двумерный массив dp[][] , в котором хранятся запомненные состояния, где dp[i][j] представляет количество последовательностей длины i , имеющих j в качестве первого элемента.
• Создайте рекурсивную функцию countSequenceUtil() , которая принимает длину последовательности и начальный элемент в качестве аргументов, устанавливает следующий элемент как кратное текущему элементу и рекурсивно вызывает оставшуюся последовательность.
• Сохраняем ответ для рассчитанных состояний в массиве dp[][] и если для какого-то состояния значение уже рассчитано, возвращаем его.
• Создайте функцию countSequence() , которая перебирает все возможные начальные элементы последовательности и вызывает рекурсивную функцию для вычисления последовательностей из K элементов с этим начальным элементом.
• Сохраните сумму рассчитанного количества для каждого начального элемента в переменной , которая является требуемым значением.

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

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