1359. Count All Valid Pickup and Delivery Options

Difficulty:
Related Topics:
Similar Questions:

    Problem

    Given n orders, each order consist in pickup and delivery services. 

    Count all valid pickup/delivery possible sequences such that delivery(i) is always after of pickup(i). 

    Since the answer may be too large, return it modulo 10^9 + 7.

      Example 1:

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

    Example 2:

    Input: n = 2
    Output: 6
    Explanation: All possible orders: 
    (P1,P2,D1,D2), (P1,P2,D2,D1), (P1,D1,P2,D2), (P2,P1,D1,D2), (P2,P1,D2,D1) and (P2,D2,P1,D1).
    This is an invalid order (P1,D2,P2,D1) because Pickup 2 is after of Delivery 2.
    

    Example 3:

    Input: n = 3
    Output: 90
    

      Constraints:

    Solution

    /**
     * @param {number} n
     * @return {number}
     */
    var countOrders = function(n) {
        return helper(n, 0, 0, {});
    };
    
    var helper = function(n, x, y, dp) {
        if (x === n && y === n) return 1;
        var mod = Math.pow(10, 9) + 7;
        var key = `${x}-${y}`;
        if (dp[key] === undefined) {
            var choosePickup = x < n ? ((n - x) * helper(n, x + 1, y, dp) % mod) : 0;
            var chooseDelivery = y < n && x > y ? ((x - y) * helper(n, x, y + 1, dp) % mod) : 0;
            dp[key] = (choosePickup + chooseDelivery) % mod;
        }
        return dp[key];
    };
    

    Explain:

    nope.

    Complexity: