Manjusaka

09-10 leetcode-1359

链接 1359. Count All Valid Pickup and Delivery Options

题目

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.

题解

这题是个归纳题，可以用分治法来做

可以这样归纳

1. 按照题意 P(N) 一定放在 D(N) 前面
2. 那么我们可以转化一个思路，每次 P 只能放在第一个，D 可以放在剩下的位置
3. 那么我们可以得出一组结论
   1. PN 有 N 种可能
   2. 确定 PN 后，DN 有 2*N -1 种选择
4. 然后不断递归即可

class Solution:
    def __init__(self):
        self.mod = 10 ** 9 + 7

    def countOrders(self, n: int) -> int:
        if n == 1:
            return 1
        return (n * (2 * n - 1) * self.countOrders(n - 1)) % self.mod