← Static tasks

1359. Count All Valid Pickup and Delivery Options

leetcode hard

#csharp#dynamic-programming#hard#leetcode#recursion

Task

Дано n заказов, каждый из которых состоит из услуги забора и доставки.

Посчитайте все возможные допустимые последовательности забора/доставки, такие что доставка(i) всегда идет после забора(i).

Поскольку ответ может быть слишком большим, верните его по модулю 10^9 + 7.

Пример

Input: n = 1

Output: 1

Explanation: Unique order (P1, D1), Delivery 1 always is after of Pickup 1.

C# solution

matched/original
public class Solution {
    public int CountOrders(int n) {
        int MOD = 1_000_000_007;
        long[] dp = new long[n + 1];
        dp[0] = 1;
        
        for (int i = 1; i <= n; i++) {
            dp[i] = dp[i - 1] * (2 * i - 1) * i % MOD;
        }
        
        return (int) dp[n];
    }
}

C++ solution

auto-draft, review before submit
#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int CountOrders(int n) {
        int MOD = 1_000_000_007;
        long[] dp = new long[n + 1];
        dp[0] = 1;
        
        for (int i = 1; i <= n; i++) {
            dp[i] = dp[i - 1] * (2 * i - 1) * i % MOD;
        }
        
        return (int) dp[n];
    }
}

Java solution

matched/original
public class Solution {
    public int countOrders(int n) {
        int MOD = 1_000_000_007;
        long[] dp = new long[n + 1];
        dp[0] = 1;
        
        for (int i = 1; i <= n; i++) {
            dp[i] = dp[i - 1] * (2 * i - 1) * i % MOD;
        }
        
        return (int) dp[n];
    }
}

Python solution

matched/original
class Solution:
    def countOrders(self, n: int) -> int:
        MOD = 10**9 + 7
        dp = [0] * (n + 1)
        dp[0] = 1
        
        for i in range(1, n + 1):
            dp[i] = dp[i - 1] * (2 * i - 1) * i % MOD
        
        return dp[n]

Go solution

matched/original
func countOrders(n int) int {
    MOD := 1_000_000_007
    dp := make([]int, n + 1)
    dp[0] = 1
    
    for i := 1; i <= n; i++ {
        dp[i] = dp[i - 1] * (2 * i - 1) * i % MOD
    }
    
    return dp[n]
}

Explanation

Algorithm

Инициализация:

Используйте динамическое программирование для хранения количества допустимых последовательностей для каждого количества заказов от 1 до n.

Рекурсивное вычисление:

Для каждого количества заказов k используйте рекурсивную формулу для вычисления количества допустимых последовательностей, учитывая, что каждая новая пара (забор и доставка) может быть вставлена в любую из существующих позиций.

Возвращение результата:

Верните результат для n заказов, применяя модуль 10^9 + 7 для предотвращения переполнения.

😎