1359. Count All Valid Pickup and Delivery Options

LeetCode hard original: C# #csharp #dynamic-programming #hard #leetcode #recursion
Il testo del problema è tradotto dal russo per la lingua selezionata. Il codice resta invariato.
LeetCode Static

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

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

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

Esempio

Input: n = 1

Output: 1

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

C# soluzione

abbinato/originale 
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++ soluzione

bozza automatica, rivedere prima dell'invio 
#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 soluzione

abbinato/originale 
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 soluzione

abbinato/originale 
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 soluzione

abbinato/originale 
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]
}

Algorithm

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

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

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

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

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

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

😎

Vacancies for this task

offerte attive with overlapping task tags are mostrati.

Tutte le offerte
Non ci sono ancora offerte attive.