Задача: 1359. Count All Valid Pickup and Delivery Options
Сложность: hard
Дано n заказов, каждый из которых состоит из услуги забора и доставки.
Посчитайте все возможные допустимые последовательности забора/доставки, такие что доставка(i) всегда идет после забора(i).
Поскольку ответ может быть слишком большим, верните его по модулю 10^9 + 7.
Пример:
Input: n = 1
Output: 1
Explanation: Unique order (P1, D1), Delivery 1 always is after of Pickup 1.
👨💻 Алгоритм:
1⃣Инициализация:
Используйте динамическое программирование для хранения количества допустимых последовательностей для каждого количества заказов от 1 до n.
2⃣Рекурсивное вычисление:
Для каждого количества заказов k используйте рекурсивную формулу для вычисления количества допустимых последовательностей, учитывая, что каждая новая пара (забор и доставка) может быть вставлена в любую из существующих позиций.
3⃣Возвращение результата:
Верните результат для n заказов, применяя модуль 10^9 + 7 для предотвращения переполнения.
😎 Решение:
class Solution {
function countOrders($n) {
$MOD = 1_000_000_007;
$dp = array_fill(0, $n + 1, 0);
$dp[0] = 1;
for ($i = 1; $i
Сложность: hard
Дано n заказов, каждый из которых состоит из услуги забора и доставки.
Посчитайте все возможные допустимые последовательности забора/доставки, такие что доставка(i) всегда идет после забора(i).
Поскольку ответ может быть слишком большим, верните его по модулю 10^9 + 7.
Пример:
Input: n = 1
Output: 1
Explanation: Unique order (P1, D1), Delivery 1 always is after of Pickup 1.
👨💻 Алгоритм:
1⃣Инициализация:
Используйте динамическое программирование для хранения количества допустимых последовательностей для каждого количества заказов от 1 до n.
2⃣Рекурсивное вычисление:
Для каждого количества заказов k используйте рекурсивную формулу для вычисления количества допустимых последовательностей, учитывая, что каждая новая пара (забор и доставка) может быть вставлена в любую из существующих позиций.
3⃣Возвращение результата:
Верните результат для n заказов, применяя модуль 10^9 + 7 для предотвращения переполнения.
😎 Решение:
class Solution {
function countOrders($n) {
$MOD = 1_000_000_007;
$dp = array_fill(0, $n + 1, 0);
$dp[0] = 1;
for ($i = 1; $i