Общее количество отсортированных чисел до N цифр в диапазоне [L, R] (комбинаторика великолепного ожерелья)

По трем целым числам N, L и R задача состоит в том, чтобы вывести общее количество способов составить ожерелье из не более чем N жемчужин, так что значения жемчужины лежат в диапазоне [L, R] и расположены в порядке возрастания .

Примеры:

Input: N = 3, L = 6, R = 9
Output: 34
Explanation:
The necklace can be formed in the following ways:

1. The necklaces of length one that can be formed are { “6”, “7”, “8”, “9” }.
2. The necklaces of length two, that can be formed are { “66”, “67”, “68”, “69”, “77”, “78”, “79”, “88”, “89”, “99” }.
3. The necklaces of length three, that can be formed are { “666”, “667”, “668”, “669”, “677”, “678”, “679”, “688”, “689”, “699”, “777”, “778”, “779”, “788”, “789”, “799”, “888”, “889”, “899”, “999” }.

Thus, in total, the necklace can be formed in (4+10+20 = 34 ) ways.

Input: N = 1, L = 8, R = 9
Output: 2
Explanation:
The necklace can be formed in the following ways: {“8”, “9”}.

Подход: Данная проблема может быть решена на основе следующих наблюдений:

1. Проблема может быть решена с помощью динамического программирования с двумя состояниями и суммой префиксов.
2. Предположим, что Dp(i, j) хранит количество способов сформировать ожерелье размера i со значениями жемчужин в диапазоне [L, j].
3. Тогда переходное состояние в i ^-й позиции можно определить как:
   1. Для каждого значения j в диапазоне [L, R]
      1. Dp(i, j) = Dp(i – 1, L) + Dp(i – 1, L + 1), …, Dp(i – 1, j – 1) + Dp(i – 1, j)
4. Приведенный выше переход можно оптимизировать, используя сумму префиксов для каждого i как:
   1. Dp(i, j) = Dp(i, L) + Dp(i, L + 1) +…+ Dp(i, j – 1) + Dp(i, j)
5. Следовательно, теперь переходы можно определить как:
   1. Dp(i, j) = Dp(i-1, j) + Dp(i, j-1)

Выполните следующие шаги, чтобы решить проблему:

• Инициализируйте переменную, скажем , как 0 , чтобы сохранить результат.
• Инициализируйте массив 2D, скажем, Dp[][] размерности N * (R – L + 1) как 0 для хранения всех состояний DP.
• Перебрать диапазон [0, N – 1] , используя переменную i, и присвоить Dp[i][0] = 1.
• Переберите диапазон [1, R – L] , используя переменную i, и обновите Dp[0][i] как Dp[0][i]= Dp[0][i – 1]+1.
• Присвойте ответу Dp[0][R – L] .
• Перебрать диапазон [1, N – 1] , используя переменную i, и выполнить следующие операции:
  • Переберите диапазон [1, R – L] , используя переменную j, и обновите Dp[i][j] как Dp[i][j] = Dp[i][j – 1] + Dp[i – 1 ][j].
  • Увеличьте ответ на Dp[i][R – L].
• Наконец, после выполнения вышеуказанных шагов, напечатайте ans .

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

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