Количество отсортированных массивов длины M, которые можно составить из первых N натуральных чисел

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

Примеры:

Input: N = 4, M = 2
Output: 10
Explanation: All such possible arrays are {1, 1}, {1, 2}, {1, 2}, {1, 4}, {2, 2}, {2, 3}, {2, 4}, {3, 3}, {3, 4}, {4, 4}.

Input: N = 2, M = 4
Output: 5
Explanation: All such possible arrays are {1, 1, 1, 1}, {1, 1, 1, 2}, {1, 1, 2, 2}, {1, 2, 2, 2}, {2, 2, 2, 2}.

Наивный подход: для каждого числа есть два варианта: его можно взять или оставить. Кроме того, число может быть взято несколько раз.

• Элементы, которые берутся несколько раз, должны быть последовательными в массиве, так как массив должен быть отсортирован.
• Если элемент оставлен и перемещен к другому элементу, то этот элемент нельзя взять снова.

Рекурсивный подход:

Левая ветвь указывает, что элемент взят, а правая ветвь указывает, что элемент оставлен и указатель переместился к следующему элементу.

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

Временная сложность: O(2 ^N )
Вспомогательное пространство: O(1)

Рекурсивный подход с оптимизацией:

• Пройдитесь по каждому элементу и попытайтесь найти все возможные массивы, начиная с этого элемента.
• В предыдущем подходе для правой ветви элемент сначала оставлялся, а на следующем шаге переходил к следующему элементу.
• В этом подходе вместо того, чтобы сначала покинуть элемент, а затем перейти к следующему элементу, сразу перейти к следующему элементу, поэтому вызовов функций будет меньше.

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

Временная сложность: O(2 ^N )
Вспомогательное пространство: O(1)

Подход динамического программирования. Можно заметить, что эта проблема имеет перекрывающиеся подзадачи и свойство оптимальной подструктуры, т. е. удовлетворяет обоим свойствам динамического программирования. Итак, идея состоит в том, чтобы использовать 2D-таблицу для запоминания результатов во время вызовов функций.

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

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

Оптимизированный по пространству подход итеративного динамического программирования:

• Поскольку все элементы доступны столько раз, сколько необходимо, поэтому нет необходимости сохранять значения для предыдущих строк, можно использовать значения из той же строки.
• Таким образом, одномерный массив можно использовать для сохранения предыдущих результатов.
• Создайте массив dp размера M , где dp[i] хранит максимальное количество отсортированных массивов размера i , которые могут быть сформированы из чисел в диапазоне [1, N] .

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

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