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

这篇具有很好参考价值的文章主要介绍了LeetCode 1359. Count All Valid Pickup and Delivery Options【动态规划,组合数学】1722。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

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

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

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

LeetCode 1359. Count All Valid Pickup and Delivery Options【动态规划,组合数学】1722,# 组合数学,动态规划,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[i1] 得到 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 i1 份订单(编号为 1 , 2 , . . . , i − 1 1, 2, ..., i - 1 1,2,...,i1 )与 1 1 1 份额外的订单(编号为 i)。对于一个包含前 i − 1 i - 1 i1 份订单的固定序列,它的长度为 ( i − 1 ) ∗ 2 (i - 1) * 2 (i1)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 (i1)2 ,那么可以添加的位置为序列的长度加 1 1 1 ,即 2 ( i − 1 ) + 1 = 2 i − 1 2(i - 1) + 1 = 2i - 1 2(i1)+1=2i1
  • 第二类: P i P_i Pi​ 和 D i D_i Di 被添加到了序列中不连续的位置,那么就相当于在 i ∗ 2 − 1 i * 2 - 1 i21 个位置中选择两个不同的位置,前者用作添加 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) (22i1)=(2i1)(i1)

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

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 j=1,2,...,i 全部判断一遍之后,我们就可以得到一个满足要求的排列了。然而这样会导致重复计数,这是因为不同的初始排列在交换顺序之后会得到相同的排列,例如当 i = 2 i = 2 i=2 时,初始排列
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!(2i1)!!
其中 ( 2 i − 1 ) ! ! = 1 ⋅ 3 ⋅ ⋯ ⋅ ( 2 i − 1 ) (2i-1)!! = 1 \cdot 3 \cdot \cdots \cdot (2i-1) (2i1)!!=13(2i1) ,其与方法一中的递推式是一致的,可以直接使用方法一的代码。文章来源地址https://www.toymoban.com/news/detail-706255.html

到了这里,关于LeetCode 1359. Count All Valid Pickup and Delivery Options【动态规划,组合数学】1722的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • leetcode - 1216. Valid Palindrome III

    Given a string s and an integer k, return true if s is a k-palindrome. A string is k-palindrome if it can be transformed into a palindrome by removing at most k characters from it. Example 1: Example 2: Constraints: Similar to 680. 验证回文字符串 Ⅱ, this time we could delete k characters. Similarly, use recursive + memo. Time complexity: o ( n k ) o

    2024年02月22日
    浏览(37)
  • Leetcode 357. Count Numbers with Unique Digits

    Given an integer n, return the count of all numbers with unique digits, x, where 0 = x 1 0 n 0 = x 10^n 0 = x 1 0 n . f(0) = 1 f(1) = 10 f(k) = 9 * 9 * 8 * … * (9 - k + 2)

    2024年02月19日
    浏览(45)
  • LeetCode2085. Count Common Words With One Occurrence

    Given two string arrays words1 and words2, return the number of strings that appear exactly once in each of the two arrays. Example 1: Input: words1 = [“leetcode”,“is”,“amazing”,“as”,“is”], words2 = [“amazing”,“leetcode”,“is”] Output: 2 Explanation: “leetcode” appears exactly once in each of the two arrays. We count this s

    2024年01月16日
    浏览(40)
  • OpenJDK 64-Bit Server VM warning: Options -Xverify:none and -noverify were deprecated in JDK 13

    OpenJDK 64-Bit Server VM warning: Options -Xverify:none and -noverify were deprecated in JDK 13 and will likely be removed in a future release 同时idea控制台出现乱码 翻译:OpenJDK 64位服务器虚拟机警告:选项-Xverify:none和-noverify在JDK 13中已被弃用,可能会在将来的版本中被删除。 方法一: Edit Configurations —

    2024年02月15日
    浏览(82)
  • LeetCode 2409. Count Days Spent Together【前缀和,容斥原理】简单

    本文属于「征服LeetCode」系列文章之一,这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁,本系列将至少持续到刷完所有无锁题之日为止;由于LeetCode还在不断地创建新题,本系列的终止日期可能是永远。在这一系列刷题文章中,我不仅会讲解多种解题思路及其优化,

    2023年04月17日
    浏览(36)
  • Java HotSpot(TM) 64-Bit Server VM warning: Options -Xverify:none and -noverify were deprecated解决方法

    Java HotSpot(TM) 64-Bit Server VM warning: Options -Xverify:none and -noverify were deprecated in JDK 13 and will likely be removed in a future release. 出现这个报错的原因是: 这是Java HotSpot™ 64位服务器虚拟机的警告消息。该警告是指在JDK 13中将选项\\\"-Xverify:none\\\"和\\\"-noverify\\\"标记为被弃用,并且在将来的版本中

    2024年02月12日
    浏览(49)
  • idea报错Java HotSpot(TM) 64-Bit Server VM warning: Options -Xverify:none and -noverify were deprecated

    最近在使用idea的时候,idea总是显示警告信息:Java HotSpot(TM) 64-Bit Server VM warning: Options -Xverify:none and -noverify were deprecated in JDK 13 and will likely be removed in a future release.  我的解决办法是: 第一步:选择下图的    Edit  Configurations 第二步:然后在跳转出的界面中找到    Enable 

    2024年02月11日
    浏览(95)
  • LeetCode每日一题——2520. Count the Digits That Divide a Number

    2520. Count the Digits That Divide a Number Given an integer num, return the number of digits in num that divide num. An integer val divides nums if nums % val == 0. Example 1: Input: num = 7 Output: 1 Explanation: 7 divides itself, hence the answer is 1. Example 2: Input: num = 121 Output: 2 Explanation: 121 is divisible by 1, but not 2. Since 1 occurs twic

    2024年02月08日
    浏览(47)
  • SpringBoot启动时出现Java HotSpot(TM) 64-Bit Server VM warning: Options -Xverify:none and -noverify were d

    // IDEA版本2022.1.4 1,首先解释一下 该错误是说,-Xverif2,解决措施 y和-noverify在JDK13版本中已经弃用了,并且以后可能会移除。 2,解决措施 RUN ----Edit Configuyation  Modify options 勾选Disable launch optimization    

    2024年02月07日
    浏览(49)
  • ssh 登录报 Authorized users only. All activities may be monitored and reported.

    ssh 登录报 Authorized users only. All activities may be monitored and reported. 解决: 修改 /etc/motd 文件,清空内容 修改以后,登录不报 Authorized users only. All activities may be monitored and reported. update 2023-12-04 12:35 如果还不行就干掉 以下两个文件的内容 /etc/issue /etc/issue.net 总结下最全方法: 方法

    2024年02月15日
    浏览(55)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包