文昌网站建设全包,邮箱购买网站,wordpress主题 时光,个旧网络推广本文属于「征服LeetCode」系列文章之一#xff0c;这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁#xff0c;本系列将至少持续到刷完所有无锁题之日为止#xff1b;由于LeetCode还在不断地创建新题#xff0c;本系列的终止日期可能是永远。在这一系列刷题文章… 本文属于「征服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 ] f[i] f[i] 表示订单数量为 i 时的序列数目我们希望通过 f [ 1 ] , f [ 2 ] , . . . , f [ i − 1 ] f[1], f[2], ..., f[i - 1] f[1],f[2],...,f[i−1] 得到 f [ i ] f[i] f[i] 的值这样就可以使用递推的方法得到 f [ n ] f[n] f[n] 了。
由于 f [ i ] f[i] f[i] 包含了 i i i 份订单我们可以将其拆分为前 i − 1 i - 1 i−1 份订单编号为 1 , 2 , . . . , i − 1 1, 2, ..., i - 1 1,2,...,i−1 与 1 1 1 份额外的订单编号为 i。对于一个包含前 i − 1 i - 1 i−1 份订单的固定序列它的长度为 ( i − 1 ) ∗ 2 (i - 1) * 2 (i−1)∗2 我们只需要在这个序列中加上第 i i i 份订单就可以得到一条订单数量为 i i i 的序列。
那么有多少种不同的方法能够加上第 i i i 份订单呢第 i 份订单包含 P i P_i Pi 和 D i D_i Di 并且 P i P_i Pi 在序列中必须出现在 D i D_i Di 之前那么我们可以将这些方法分成两类
第一类 P i P_i Pi 和 D i D_i Di 被添加到了序列中连续的位置。由于序列的长度为 ( i − 1 ) ∗ 2 (i - 1) * 2 (i−1)∗2 那么可以添加的位置为序列的长度加 1 1 1 即 2 ( i − 1 ) 1 2 i − 1 2(i - 1) 1 2i - 1 2(i−1)12i−1 第二类 P i P_i Pi 和 D i D_i Di 被添加到了序列中不连续的位置那么就相当于在 i ∗ 2 − 1 i * 2 - 1 i∗2−1 个位置中选择两个不同的位置前者用作添加 P i P_i Pi 后者用作添加 D i D_i Di 方法数为组合数 ( 2 i − 1 2 ) ( 2 i − 1 ) ( i − 1 ) \binom{2i - 1}{2} (2i - 1)(i - 1) (22i−1)(2i−1)(i−1) 。
将这两类的方法数量相加就可以得到对于一个固定的包含前 i − 1 i - 1 i−1 份订单的固定序列用 ( 2 i − 1 ) i (2i-1)i (2i−1)i 种方法可以加入第 i i i 份订单。由于前 i − 1 i - 1 i−1 份订单对应的序列数目为 f [ i − 1 ] f[i - 1] f[i−1] 并且对于任意两个不同的包含前 i − 1 i - 1 i−1 份订单的序列都不会因为加上第 i i i 份订单使得它们变得相同。因此我们就得到了递推公式 f [ i ] ( 2 i − 1 ) i ∗ f [ i − 1 ] f[i] (2i−1)i∗f[i−1] f[i](2i−1)i∗f[i−1] 由于递推公式中 f [ i ] f[i] f[i] 仅与 f [ i − 1 ] f[i - 1] f[i−1] 有关我们在递推式可以只存储 f [ i − 1 ] f[i - 1] f[i−1] 的值而不用把 f [ 1 ] , f [ 2 ] , . . . , f [ i − 1 ] f[1], f[2], ..., 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(N) O(N) 。空间复杂度 O ( 1 ) O(1) O(1) 。 解法2 整体法
除了递推法之外我们也可以从整体进行考虑直接得到 f [ i ] f[i] f[i] 的通项公式。
假设现在没有 D i D_i Di 必须在 P i P_i Pi 之后的要求那么 f [ i ] ( 2 i ) ! f[i] (2i)! f[i](2i)! 这是因为我们可以将 P 1 , D 1 , P 2 , D 2 , ⋯ , P i , D i P_1, D_1, P_2, D_2, \cdots, P_i, D_i P1,D1,P2,D2,⋯,Pi,Di 的任意一个排列作为答案排列的数目为 ( 2 i ) ! (2i)! (2i)! 。我们称这些排列为初始排列。
那么在加上了「 D i D_i Di 必须在 P i P_i Pi 之后」的要求后有一些初始排列就不能作为答案了。但是我们可以对它们进行调整使它们变成满足要求的排列。具体地对于任意一个初始排列如果第 j j j 个物品的 D j D_j Dj 出现在 P j P_j Pj 之前那么我们就把 D j D_j Dj 和 P j P_j Pj 交换顺序。在对 j 1 , 2 , . . . , i j 1, 2, ..., i j1,2,...,i 全部判断一遍之后我们就可以得到一个满足要求的排列了。然而这样会导致重复计数这是因为不同的初始排列在交换顺序之后会得到相同的排列例如当 i 2 i 2 i2 时初始排列 D 1 , D 2 , P 1 , P 2 D 1 , P 2 , P 1 , D 2 \begin{aligned}D1, D2, P1, P2 \\ D1, P2, P1, D2\end{aligned} D1,D2,P1,P2D1,P2,P1,D2 在交换后都会得到相同的排列 P 1 , P 2 , D 1 , D 2 P1, P2, D1, D2 P1,P2,D1,D2 如何去除重复计数呢我们可以进行逆向思考反过来计算一个排列可以从多少个初始排列得来。显然对于排列中的 i i i 对 P j P_j Pj 和 D j D_j Dj 我们将其中任意数量的对交换顺序都可以得到一个不同的初始排列。交换顺序的选择有 2 i 2^i 2i 种每一对 P j P_j Pj 和 D j D_j Dj 交换或不交换因此一个排列对应着 2 i 2^i 2i 个初始排列即排列的数目为 f [ i ] ( 2 i ) ! 2 i f[i] \frac{(2i)!}{2^i} f[i]2i(2i)!
这样就得到了 f [ i ] f[i] f[i] 的通项公式。由于通项公式中包含除法在取模的意义下不好直接计算我们可以将分母 2 i 2^i 2i 拆分成 i i i 个 222与分子阶乘中的 i i i 个偶数相除得到 f [ i ] i ! ( 2 i − 1 ) ! ! f[i] i!(2i-1)!! f[i]i!(2i−1)!! 其中 ( 2 i − 1 ) ! ! 1 ⋅ 3 ⋅ ⋯ ⋅ ( 2 i − 1 ) (2i-1)!! 1 \cdot 3 \cdot \cdots \cdot (2i-1) (2i−1)!!1⋅3⋅⋯⋅(2i−1) 其与方法一中的递推式是一致的可以直接使用方法一的代码。
