题目大意：
有效的快递序列数目
给你 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
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1359
解题思路分析：
这是一道典型的动态规划问题。用数学语言来描述的话，题目实际上在求所有接单和发单的排列组合。解题时，我们需要定义当前没有接的单子数量n，以及手中还未发送的单子数量p。初始时，n等于题目给出的单子数量，p等于0。对于任意一个时间点，如果n大于0，说明我们可以接一单，n个单子中的任意一单都是我们可以接收的对象，接收后n的数量减一，同时手中单子数量p加一，因此当前时间点接收一单的可能性为：
res = n * help(p+1, n-1);
另外，在当前时间点，如果手中的单子数量p大于0，我们也可以选择发单，发单时可以在p个单子中任选一个发送，发送后，p的数量减一，而n不变，因此当前时间点发送一单的可能性为：
res = p * help(p-1, n);
将上面两个结果相加即是当前时间点所有操作的排列组合数。
另外递归时，我们需要使用记忆数组来作为辅助，避免重复情况的计算。
如果你对动态规划解法或者是记忆数组还不太了解，可以参照我之前分享过的文章：
实现代码：
int[][] memo; // 记忆数组
public int countOrders(int n) {
// 初始化记忆数组
memo=new int[n+1][n+1];
// 递归求解
return help(0,n);
}
// p为手中的单子数
// n为还未接收的单子数
// 返回值为，手中有p个单子，并且还有n个单子未接收的情况下的排列组合数
int help(int p, int n){
// 如果p和n都是0，默认返回1
if(n==0&&p==0) return 1;
// 如果记忆数组中存在当前解，直接返回
if(memo[p][n]>0)return memo[p][n];
// 返回结果
int res=0;
// 如果还有未接的单子，我们可以选择接一单
if(n>0){
// 从n个未接的单子中任意接一单后的组合数
res+=((long)n*help(p+1,n-1)%1000000007);
}
// 如果还有未发送的单子，我们可以选择发送一单
if(p>0){
// 从n个未发送的单子中任意发送一单后的组合数
res+=((long)p*help(p-1,n)%1000000007);
}
// 将当前结果保存至记忆数组
memo[p][n]=res;
// 返回当前结果
return res;
}本题解法执行时间为30ms。
Runtime: 30 ms, faster than 8.67% of Java online submissions for Count All Valid Pickup and Delivery Options.
Memory Usage: 41 MB, less than 100.00% of Java online submissions for Count All Valid Pickup and Delivery Options.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: https://leetcode.jp/leetcode-1359-count-all-valid-pickup-and-delivery-options-解题思路分析/