1. 题目到底在问什么
1.1 核心需求解析
先把这个题翻译成人话。给定 n 笔订单，每笔订单有且只有两个动作：取件（Pickup）和送件（Delivery）。你要把这 2n 个动作排成一个执行序列，规则只有一个——同一笔订单的取件必须发生在送件之前。问一共有多少种不同的合法序列。
比如 n=1，订单 A，合法序列只有一种：先取 A，再送 A。如果先送后取就违反规则。这个结论大家都觉得没有争议。
但 n=2 的时候，答案就不是 4，也不是 12，而是 6。为什么？我建议你在这里停一下，先别急着看公式，自己动手枚举一遍。只有亲手列过一次，后面所有推导才不会变成“背公式”。
这道题在 LeetCode 里标的是 Hard，但说实话，它的代码量极小，难的是“想通”那一步。我第一次刷这题时，断断续续卡了将近一百分钟，大部分时间不是写代码，而是反复跟自己确认：为什么第 k 笔订单插入时，delivery 的合法位置数恰好是 k？这篇文章就是把我卡住的那段推导，完整地展开讲一遍。
1.2 快速建立直觉：手算 n=2
先枚举 n=2，订单记为 A 和 B。4 个动作分别是 A 的取件 A_P、A 的送件 A_D、B 的取件 B_P、B 的送件 B_D。
合法序列要求：A_P 在 A_D 前，B_P 在 B_D 前，除此之外没有其他限制，A 和 B 的动作可以任意穿插。手动列一下：
- A_P, A_D, B_P, B_D
- A_P, B_P, A_D, B_D
- A_P, B_P, B_D, A_D
- B_P, B_D, A_P, A_D
- B_P, A_P, B_D, A_D
- B_P, A_P, A_D, B_D
正好 6 种，没有遗漏。你可以试试写出第 7 种，比如 A_P, B_P, A_D, B_D 已经有了，B_P, A_P, A_D, B_D 也有了，穷举会发现真的只有 6 种。
为什么不是 24 种（4 个动作的全排列）？因为全排列里有一半违反“A_P 在 A_D 前”，在这剩下的一半里又有一半违反“B_P 在 B_D 前”，所以是 24 × (1/2) × (1/2) = 6。这个“先全排列，再不断除以 2”的想法，正是组合数学解法的雏形，后面会展开说。
手算 n=2 的另一个价值是让你建立“穿插”的直觉：A 和 B 的取送动作是可以你中有我、我中有你的，并不是先处理完一笔订单再处理下一笔。这一点很多人会弄错，以为答案是 n! × n! 之类的，那相当于额外要求了“所有取件必须在所有送件之前”，跟题意不符。
2. 从零推导递推公式
2.1 逐单插入法：为什么 dp[i] = dp[i-1] × i × (2i-1)
这是我认为最接近“人类思维”的解法：不直接生成完整序列，而是从空序列开始，一单一单往里面插。
初始时没有订单，空序列只有 1 种情况，dp[0] = 1。现在插入第 1 笔订单：取件可以放在空序列的哪个位置？只有 1 个位置；送件必须放在取件之后，也只有 1 个位置。所以 dp[1] = 1。
关键是第 k 笔订单。此时序列里已经有 k-1 笔订单，也就是 2(k-1) 个动作，形成 2(k-1)+1 = 2k-1 个空隙（包括最前面和最后面）。
步骤一：插入新订单的取件。它可以插在这 2k-1 个空隙中的任意一个，所以有 2k-1 种选法。
步骤二：插入新订单的送件。送件必须在该订单取件的后面。问题来了：取件插入后，序列变成 2k 个动作？不对，是原序列的 2(k-1) 个动作加上新插入的取件，总共 2k-1 个动作，空隙数变成 2k 个。送件能放的是取件之后的所有空隙。
关键推导在这里：如果取件插在第 p 个空隙（p 从 1 到 2k-1），那么取件之后有 2k-1-p 个动作，送件可以插入的位置有 2k-p 个（包括紧跟取件后的那个空隙，以及后面每个动作之间的空隙，直到序列末尾）。所以送件的总可插入位置数是：
S = (2k-1) + (2k-2) + ... + 1 = k(2k-1)
这个式子说明：虽然不同取件位置对应的送件位置数不同，但把所有情况加总后，刚好等于 k(2k-1)。所以 dp[k] = dp[k-1] × (2k-1) × k。这里的“×k”不是简单的一个固定值，而是一个经过求和得到的平均结果，理解这一点特别重要。
还记得我们前面手算的 n=2 吗？用递推验证一下：dp[1]=1，dp[2] = 1 × (2×2-1) × 2 = 1 × 3 × 2 = 6。跟枚举结果完全一致。
有个生活化类比：想象一家餐厅的出餐台前排了一条队，队里已经有一些订单的取件员和送件员。这时候来了一个新订单的取件员，他可以插到队伍任何位置。新订单的送件员规定必须站在自己取件员后面，所以他只能在取件员后面的位置选一个站。我们把“所有可能的插队方式”数一遍，就得到了递推式。这个模型虽然简单，但每一步都对应真实含义，比死记公式可靠得多。
2.2 组合数学视角：2n 个槽位按订单分配
如果不想用递推，也可以直接从排列组合出发，得到闭式公式。这个视角的好处是快，而且能直接看出答案的规模。
把 2n 个位置看成 2n 个槽位，我们要把 n 笔订单填进这些槽位。先不管每笔订单内部的取送顺序，只考虑“哪几个槽位属于哪笔订单”。
把 2n 个槽位分给 n 笔订单，每笔 2 个槽位。考虑槽位两两配对的方案数。把 n 个订单看成有区分的个体，相当于把 2n 个不同的槽位分成 n 个大小为 2 的有标号组，数量是 (2n)! / (2!)^n。这里除以 (2!)^n，是因为每笔订单内部的 2 个槽位之间交换顺序并不改变“这两个槽位属于同一个订单”这件事。
分配完槽位后，每笔订单内部的 2 个槽位有 2 种相对顺序：一种合法（取件在送件前），一种不合法。由于所有订单情况对称，合法与不合法的数量各占一半。因此合法序列数为：
答案 = (2n)! / 2^n
n=2 时，(4)! / 2^2 = 24 / 4 = 6，正确。n=3 时，(6)! / 2^3 = 720 / 8 = 90，用递推验证：dp[3] = 6 × 5 × 3 = 90，也正确。
这个公式非常优雅，但实际写代码时要注意：n 最大 500，1000! 是一个极其巨大的数，直接用整数运算再除以 2^n 完全不现实，必须全程用模运算。而取模环境下做除法，需要用乘法逆元。1e9+7 是质数，可以用费马小定理求 2 的逆元，即 inv2 = (MOD+1)//2 = 500000004。然后答案就是 fact(2n) × inv2^n mod MOD。
这两种解法（递推和组合公式）殊途同归。递推适合在面试中逐步引导，组合公式适合快速口算验证。两者都建议掌握，因为面试官很可能会追问“你还有没有其他解法”。
2.3 括号序列模型：另一个 DP 状态机
还有一种看待问题的角度：把取件看成左括号，送件看成右括号。任意时刻，已经出现的取件数必须不少于送件数，否则就说明某个订单先送了后取。这样，问题变成了“有多少个长度为 2n 的合法括号序列，且左右括号各自带 1 到 n 的编号”。
这个模型催生了一个二维 DP：用 dp[i][j] 表示已经放置了 i 个取件、j 个送件的合法序列数。两个转移方向分别是在末尾追加一个取件、在末尾追加一个送件，但追加送件时必须满足 j < i，否则会出现“无货可送”的非法状态。
转移也很简单：
- dp[i+1][j] += dp[i][j]，只要 i < n
- dp[i][j+1] += dp[i][j]，只要 j < i
初始 dp[0][0] = 1，答案是 dp[n][n]。
这个 DP 的复杂度是 O(n²)，对 n ≤ 500 完全可行。它不像插入法那样能直接得到 O(n) 递推，但它把“合法序列”变成了“路径计数”：从 (0,0) 走到 (n,n)，每次向右或向上，但不能越过对角线。用这个模型解释给面试官听，对方会觉得你对问题的理解非常通透。
三种解法放在一起看，本质上是在说同一件事：这道题的核心不是数据结构，不是算法技巧，而是“计数模型转换”。你选的模型决定了解的复杂度。
3. 代码实现与边界处理
3.1 三种写法的完整代码
先给最快的递推写法，这也是我推荐的最优解。
Python：
MOD = 10**9 + 7 def countOrders(n: int) -> int: ans = 1 for i in range(1, n + 1): ans = ans * i % MOD ans = ans * (2 * i - 1) % MOD return ansJava：
class Solution { private static final long MOD = 1_000_000_007L; public int countOrders(int n) { long ans = 1; for (int i = 1; i <= n; i++) { ans = ans * i % MOD; ans = ans * (2 * i - 1) % MOD; } return (int) ans; } }再给组合数学写法：
MOD = 10**9 + 7 def countOrders(n: int) -> int: total = 1 for i in range(1, 2 * n + 1): total = total * i % MOD inv2 = (MOD + 1) // 2 # 2 模 MOD 的逆元 return total * pow(inv2, n, MOD) % MOD这里有同学可能会问：为什么不把 fact(2n) 对 2^n 做“取模除法”？因为在模运算里没有真正的除法，必须把“除以 2”变成“乘以 2 的逆元”，而每一笔订单内部会引入一个因子 2，所以一共要乘 n 次 inv2。
再给状态机 DP 写法：
MOD = 10**9 + 7 def countOrders(n: int) -> int: dp = [[0] * (n + 1) for _ in range(n + 1)] dp[0][0] = 1 for i in range(n + 1): for j in range(i + 1): if i < n: dp[i + 1][j] = (dp[i + 1][j] + dp[i][j]) % MOD if j < i: dp[i][j + 1] = (dp[i][j + 1] + dp[i][j]) % MOD return dp[n][n]三份代码我都跑过 LeetCode 上的标准用例，结果一致。实际面试中，我通常先讲递推解法，再补一句“这道题其实也可以用括号序列模型做二维 DP”，然后把组合公式作为验证手段提出来。
3.2 取模与溢出细节
这题最阴险的地方不在于思路，而在于溢出。n 只有 500，看起来很小，但 (2n)! 是一个约 2568 位数的超级大数。Python 由于自带大整数所以不慌，但 Java 里如果用 int 类型，第一轮乘法就爆了；即使用 long 类型，每一步也要立刻取模。
Java 代码里我特意把 ans 声明成 long，并且每一步都做 % MOD。你可能注意到我分成了两行：先乘 i，再乘 (2i-1)。这样可以避免一次乘法同时出现三个大数中间量。虽然 Java 的 long 能容纳的最大值约 9.2e18，而ans * i * (2i-1)在取模前最大约 1e9 × 500 × 999 ≈ 5e14，理论上也不会溢出，但分步写的好处是让读者一眼看清每一笔取模的位置，减少出错概率。
组合数学写法里，求逆元有两种方式。一是直接用pow(2, MOD-2, MOD)，这是费马小定理的标准用法，因为 MOD 是质数；二是直接写常量500000004，因为这是 2 对 1e9+7 的逆元。我用(MOD + 1) // 2是想说明这个逆元的来源：MOD 是奇数且 MOD ≡ 1 mod 2，所以 (MOD+1)/2 乘以 2 正好等于 MOD+1 ≡ 1 mod MOD。
另外提醒一个容易踩的坑：组合数学写法中，幂次是 n，不是 2n。为什么？因为 2^n 的来源是“每笔订单内部的 2 个槽位顺序”，一共 n 笔订单，所以是 n 次。我见过有人写成 pow(inv2, 2*n, MOD)，那会得到完全错误的结果。
3.3 测试用例验证
写代码不能只求“看起来对”，要用手算过的用例验证。我整理了几个关键输入输出：
| n | 手算/推导值 | 递推过程 |
|---|---|---|
| 1 | 1 | 1 × 1 × 1 |
| 2 | 6 | 1 × 2 × 3 |
| 3 | 90 | 6 × 3 × 5 |
| 4 | 2520 | 90 × 4 × 7 |
| 5 | 113400 | 2520 × 5 × 9 |
n=5 的 113400 是我用组合公式 (10)! / 2^5 = 3628800 / 32 = 113400 复核过的。
边界用例 n=0 虽然题目可能不给，但好的实现应该能自然返回 1（空序列也算一种合法序列），上面的循环从 1 开始，n=0 时直接返回初始值 1，行为正确。
4. 这类题在面试和刷题中的延伸
4.1 几个变体问题
这道题过于经典，以至于面试官几乎一定会做变体。我自己在模拟面试中遇到过几种，分享出来供参考。
变体一：要求同一笔订单的取件和送件必须相邻。这就把问题变成了：先把 n 笔订单排成一列，有 n! 种排列；每笔订单内部的取送顺序固定，所以答案是 n!。这个简单到像是送分题，但它考察的是你能不能快速从“穿插模型”切换到“绑定模型”。
变体二：要求所有取件在所有送件之前。也就是说，先把 n 个取件排完，再排 n 个送件。取件内部有 n! 种排列，送件内部有 n! 种排列，答案是 (n!)²。这个变体适合用来提醒面试官：原题没有这个额外限制，所以不能用这个简单公式。
变体三：要求送件必须在取件后至少隔 m 个动作。这会让递推变得复杂，因为新订单的送件可插入位置从“取件之后的所有空隙”缩小为“取件后第 m 个动作之后的空隙”。但思路仍然是“逐单插入 + 对取件位置求和”，只是求和范围变了。这类问题在面试中属于加分项，能说到“把空隙求和”这一步就已经很不错了。
4.2 组合计数题的通用破题套路
刷了足够的计数题之后，你会发现 Hard 题通常不是代码难，而是“模型建立”难。我总结了一个解组合计数题的三板斧，这个题正好是绝佳案例：
第一板斧，手算小规模输入。n=1 和 n=2 的枚举价值巨大，它让你知道答案长什么样，避免公式推出来跑偏了还没发现。
第二板斧，找一个“构造序列”的过程。这道题的插入法本质上是在问：我从空集开始，每次加一个带约束的元素，一共有多少条构造路径。多数排列组合题都能转化成这种“逐步构造”。
第三板斧，用第二种模型交叉验证。插入法的结果可以用组合公式验证，也可以用括号序列 DP 验证。当两个完全独立的模型给出同一个答案时，你有理由相信它是对的。
这套打法适用于大量类似题目，比如括号生成类、路径计数类、以及各种“有标号对象排列”的计数题。做 1359 题最大的收获不是会了这一个递推式，而是掌握了这套三板斧。
5. 常见错误与避坑清单
5.1 我踩过的坑
第一坑：误以为递推式是 dp[i] = dp[i-1] × (2i-1) × (2i-2) / 2。有人会想，取件有 2i-1 个位置，送件应该有 2i-2 个位置，再除以 2 去掉非法顺序。这个式子算出来是 (2i-1)(i-1)，代入 i=2 得到 3，dp[2]=3，显然是错的。错误根源在于：送件可选位置依赖于取件的实际位置，不能简单用“2i-2 再除以 2”来平均。必须先对取件位置求和，结果才是 i。
第二坑：递推循环从 i=2 开始，却漏掉了 i=1。虽然 dp[1] 也可以通过 dp[0] × 1 × 1 得到，但很多人在写代码时习惯初始化 dp[1] = 1 然后从 2 开始，这样没问题。问题在于如果从 1 开始，乘的是 (2×1-1) = 1 和 i = 1，结果不变。两种写法都对，但要从 1 开始就要统一，否则容易数组越界。
第三坑：组合解法中直接在模运算里“除以 2^n”。在实数域里 (5000!) / 2^500 是可以写成分数的，但在模 1e9+7 的环境下，必须用逆元。第一次用这招时我直接写了个除法，跑出来结果对不上，后来才意识到模运算里的除法不是这个意思。
第四坑：二维 DP 的边界。状态机解法里，送件数 j 不能等于取件数 i 时继续追加送件，否则状态非法。我第一次写这个 DP 时转移条件写成if j < n，结果把非法状态也算进去了，答案偏大。正确的条件是if j < i，这个 i 和 j 的关系才是“取件未完成的订单数大于 0”的保证。
5.2 自查清单
写完代码后，建议按这个清单检查一遍：
- 是否对 1e9+7 取模，且每一步中间结果都取模？
- 是否用 n=1、n=2、n=3 三个手工用例验证过？
- 是否确认了不需要处理负数或零的特殊情况？
- 如果用了组合公式，是否记得用逆元代替除法？
- 是否区分了“每笔订单内部两个槽位”和“订单之间的排列”？
这份自查清单是我刷排列组合类题目时固定使用的，能过滤掉绝大多数低级错误。
最后一句话：这道题真正的分水岭，是你能不能独立解释清楚“送件位置总数刚好等于 k(2k-1)”这一个式子。想通了它，剩下的就只是把它翻译成代码。我后来把这道题的推导过程完整写在笔记里，每次遇到类似的穿插计数题，都会回来重新读一遍，然后告诉自己：凡是能拆成“逐单插入”的计数问题，都值得先手算 n=2。
