LeetCode 1359. Count All Valid Pickup and Delivery Options【动态规划,组合数学】1722

本文属于「征服LeetCode」系列文章之一，这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁，本系列将至少持续到刷完所有无锁题之日为止；由于LeetCode还在不断地创建新题，本系列的终止日期可能是永远。在这一系列刷题文章中，我不仅会讲解多种解题思路及其优化，还会用多种编程语言实现题解，涉及到通用解法时更将归纳总结出相应的算法模板。

为了方便在PC上运行调试、分享代码文件，我还建立了相关的仓库。在这一仓库中，你不仅可以看到LeetCode原题链接、题解代码、题解文章链接、同类题目归纳、通用解法总结等，还可以看到原题出现频率和相关企业等重要信息。如果有其他优选题解，还可以一同分享给他人。

由于本系列文章的内容随时可能发生更新变动，欢迎关注和收藏征服LeetCode系列文章目录一文以作备忘。

给你 n 笔订单，每笔订单都需要快递服务。

请你统计所有有效的 收件/配送 序列的数目，确保第 i 个物品的配送服务 delivery(i) 总是在其收件服务 pickup(i) 之后。

由于答案可能很大，请返回答案对 10^9 + 7 取余的结果。

示例 1：

输入：n = 1
输出：1
解释：只有一种序列 (P1, D1)，物品 1 的配送服务（D1）在物品 1 的收件服务（P1）后。

示例 2：

输入：n = 2
输出：6
解释：所有可能的序列包括：
(P1,P2,D1,D2)，(P1,P2,D2,D1)，(P1,D1,P2,D2)，(P2,P1,D1,D2)，(P2,P1,D2,D1) 和 (P2,D2,P1,D1)。
(P1,D2,P2,D1) 是一个无效的序列，因为物品 2 的收件服务（P2）不应在物品 2 的配送服务（D2）之后。

示例 3：

输入：n = 3
输出：90

提示：

• 1 <= n <= 500

---

解法 动态规划+组合数学+递推

设 $f[i]$ 表示订单数量为 i 时的序列数目，我们希望通过 $f[1],f[2],...,f[i-1]$ 得到 $f[i]$ 的值，这样就可以使用递推的方法得到 $f[n]$ 了。

由于 $f[i]$ 包含了 $i$ 份订单，我们可以将其拆分为前 $i-1$ 份订单（编号为 $1,2,...,i-1$ ）与 $1$ 份额外的订单（编号为 i）。对于一个包含前 $i-1$ 份订单的固定序列，它的长度为 $(i-1)\ast 2$ ，我们只需要在这个序列中加上第 $i$ 份订单，就可以得到一条订单数量为 $i$ 的序列。

那么有多少种不同的方法能够加上第 $i$ 份订单呢？第 i 份订单包含 $P_i$ 和 $D_i$ ，并且 $P_i$ 在序列中必须出现在 $D_i$ 之前，那么我们可以将这些方法分成两类：

• 第一类：$P_i$ 和 $D_i$ 被添加到了序列中连续的位置。由于序列的长度为 $(i-1)\ast 2$ ，那么可以添加的位置为序列的长度加 $1$ ，即 $2(i-1)+1=2i-1$ ；
• 第二类：$P_i$​ 和 $D_i$ 被添加到了序列中不连续的位置，那么就相当于在 $i\ast 2-1$ 个位置中选择两个不同的位置，前者用作添加 $P_i$ ，后者用作添加 $D_i$ ，方法数为组合数 $\left(\genfrac{}{}{0ex}{}{2i-1}{2}\right)=(2i-1)(i-1)$ 。

将这两类的方法数量相加，就可以得到：对于一个固定的包含前 $i-1$ 份订单的固定序列，用 $(2i-1)i$ 种方法可以加入第 $i$ 份订单。由于前 $i-1$ 份订单对应的序列数目为 $f[i-1]$ ，并且对于任意两个不同的包含前 $i-1$ 份订单的序列，都不会因为加上第 $i$ 份订单使得它们变得相同。因此我们就得到了递推公式：
$$f[i]=(2i-1)i\ast f[i-1]$$
由于递推公式中 $f[i]$ 仅与 $f[i-1]$ 有关，我们在递推式可以只存储 $f[i-1]$ 的值，而不用把 $f[1],f[2],...,f[i-1]$ 都记录下来。

using LL = long long;class Solution {
private:static constexpr int mod = 1000000007;
public:int countOrders(int n) {if (n == 1) return 1;int ans = 1;for (int i = 2; i <= n; ++i)ans = (LL)ans * (i * 2 - 1) % mod * i % mod;return ans;}
};

复杂度分析：

• 时间复杂度：$O(N)$ 。
• 空间复杂度：$O(1)$ 。

---

解法2 整体法

除了递推法之外，我们也可以从整体进行考虑，直接得到 $f[i]$ 的通项公式。

假设现在没有 $D_i$ 必须在 $P_i$ 之后的要求，那么
$$f[i]=(2i)!$$
这是因为我们可以将 $P_1,D_1,P_2,D_2,\cdots ,P_i,D_i$ 的任意一个排列作为答案，排列的数目为 $(2i)!$ 。我们称这些排列为初始排列。

那么在加上了「 $D_i$ 必须在 $P_i$ 之后」的要求后，有一些初始排列就不能作为答案了。但是我们可以对它们进行调整，使它们变成满足要求的排列。具体地，对于任意一个初始排列，如果第 $j$ 个物品的 $D_j$ 出现在 $P_j$ 之前，那么我们就把 $D_j$ 和 $P_j$ 交换顺序。在对 $j=1,2,...,i$ 全部判断一遍之后，我们就可以得到一个满足要求的排列了。然而这样会导致重复计数，这是因为不同的初始排列在交换顺序之后会得到相同的排列，例如当 $i=2$ 时，初始排列
$$\begin{array}{r}D1,D2,P1,P2\\ D1,P2,P1,D2\end{array}$$
在交换后都会得到相同的排列 $P1,P2,D1,D2$ 如何去除重复计数呢？我们可以进行逆向思考，反过来计算一个排列可以从多少个初始排列得来。显然，对于排列中的 $i$ 对 $P_j$ 和 $D_j$ ，我们将其中任意数量的对交换顺序，都可以得到一个不同的初始排列。交换顺序的选择有 $2^i$ 种（每一对 $P_j$ 和 $D_j$​ 交换或不交换），因此一个排列对应着 $2^i$ 个初始排列，即排列的数目为：
$$f[i]=\frac{(2i)!}{2^i}$$

这样就得到了 $f[i]$ 的通项公式。由于通项公式中包含除法，在取模的意义下不好直接计算，我们可以将分母 $2^i$ 拆分成 $i$ 个 222，与分子阶乘中的 $i$ 个偶数相除，得到
$$f[i]=i!(2i-1)!!$$
其中 $(2i-1)!!=1\cdot 3\cdot \cdots \cdot (2i-1)$ ，其与方法一中的递推式是一致的，可以直接使用方法一的代码。