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 ] 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)+1=2i−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 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!(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) ,其与方法一中的递推式是一致的,可以直接使用方法一的代码。
相关文章:

LeetCode 1359. Count All Valid Pickup and Delivery Options【动态规划,组合数学】1722
本文属于「征服LeetCode」系列文章之一,这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁,本系列将至少持续到刷完所有无锁题之日为止;由于LeetCode还在不断地创建新题,本系列的终止日期可能是永远。在这一系列刷题文章…...

[杂谈]-从硬件角度理解二进制数
从硬件角度理解二进制数 文章目录 从硬件角度理解二进制数1、概述2、模拟电路3、数字电路4、逻辑电平5、TTL 器件的电压水平6、总结 1、概述 二进制数以 2 为基数系统表示,该系统只有两 (2) 个不同的数值,即 0 和 1。就像最常见的那样,十进制…...

Fast-DDS 服务发现简要概述
阅读本文章需要对DDS基础概念有一些了解,一些内容来自Fast-DDS官方文档,一些是工作中踩过的坑。 1. 服务发现阶段 满足OMG标准的DDS服务发现分为两部分,分别是: PDP(Participant Discovery Protocol 参与者发现协议):参与者确认…...

基于spingboot的websocket订阅、广播、多人聊天室示例
概述 基于spingboot的websocket多人聊天系统。包括订阅,广播、点对点单人聊天,多人聊天室功能。 详细 一、运行效果 简单示例 广播 单人聊天 多人聊天室 二、相关代码 websocket配置 package com.iamgpj.demowebsocket.config;import com.iamgpj.d…...

Linux mac Windows三系统 局域网文件共享方法
主要工具: Samba是一个开源的软件套件,允许Linux系统与Windows系统之间共享文件和打印机。 一、首先是Linux共享的设置 ①安装 sudo apt-get install samba ②创建共享文件夹 sudo mkdir /home/share ③配置用户 sudo smbpasswd -a kequan ④修改…...

Java——比较器
引入的背景 我们知道基本数据类型的数据(除boolean类型外)需要比较大小的话,直接使用比较运算符即可,但是引用数据类型是不能直接使用比较运算符来比较大小的。那么,如何解决这个问题呢? 在Java中经常会涉…...
【数据结构】初识泛型
文章目录 一般的类和方法,只能使用具体的类型: 要么是基本类型,要么是自定义的类。这种限制对代码的束缚就会很大。所以我们引入了泛型。泛型,泛顾名思义就是广泛的意思。就是适用于许多许多类型。从代码上讲,就是对类型实现了参数…...
代码随想录--哈希--有效的字母异位词
给定两个字符串 s 和 t ,编写一个函数来判断 t 是否是 s 的字母异位词。 示例 1: 输入: s "anagram", t "nagaram" 输出: true 示例 2: 输入: s "rat", t "car" 输出: false 说明: 你可以假设字符串只包含小写字母。…...
MySQL——数据的增删改
2023.9.12 本章开始学习DML (数据操纵语言) 语言。相关学习笔记如下: #DML语言 /* 数据操作语言: 插入:insert 修改:update 删除:delete */#一、插入语句 #方式一:经典的插入 /* 语法: insert …...

云服务器与http服务器
如何与http服务器建立连接(客户端)? http请求设计格式: 例子: 发送http请求 http数据响应格式: 接收http服务器返回的数据需要进一步进行字符串处理操作,提取有用的数据。...

golang教程 beego框架笔记一
安装beego 安装bee工具 beego文档 # windos 推荐使用 go install github.com/beego/bee/v2master go get -u github.com/beego/bee/v2masterwindows使用安装bee工具时碰到的问题; 环境配置都没有问题,但是执行官网的命令:go get -u github…...

【深度学习】Mini-Batch梯度下降法
Mini-Batch梯度下降法 在开始Mini-Batch算法开始之前,请确保你已经掌握梯度下降的最优化算法。 在训练神经网络时,使用向量化是加速训练速度的一个重要手段,它可以避免使用显式的for循环,并且调用经过大量优化的矩阵计算函数库。…...

AI项目六:WEB端部署YOLOv5
若该文为原创文章,转载请注明原文出处。 一、介绍 最近接触网页大屏,所以就想把YOLOV5部署到WEB端,通过了解,知道了两个方法: 1、基于Flask部署YOLOv5目标检测模型。 2、基于Streamlit部署YOLOv5目标检测。 代码在…...
敲代码常用快捷键
1、代码拖动 PyCharm:按住 shiftalt鼠标选中某一区域来拖动,即可实现拖动这一区域至指定区域。Visual Studio Code (VSCode): - Windows/Linux:Alt 鼠标左键拖动 - MacOS:Option 鼠标左键拖动 IntelliJ IDEA: - Win…...
MyBatis: 分页插件PageHelper直接传递分页参数的用法
一、加分页插件依赖 <dependency><groupId>com.github.pagehelper</groupId><artifactId>pagehelper-spring-boot-starter</artifactId><version>1.2.13</version></dependency>二、配置分页插件,并配置相关属性&a…...

Python基于Flask的高校舆情分析,舆情监控可视化系统
博主介绍:✌程序员徐师兄、7年大厂程序员经历。全网粉丝30W,Csdn博客专家、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和毕业项目实战✌ 运行效果图 基于Python的微博大数据舆情分析,舆论情感分析可视化系统 系统介绍 微博舆情分析系…...

Python第一次作业练习
题目分析: """ 参考学校的相关规定。 对于四分制,百分制中的90分及以上可视为绩点中的4分,80 分及以上为3分,70 分以上为2分,60 分以上为1分; 五分制中的5分为四分制中的4分,4分为3分&#…...

InstallShield打包升级时不覆盖原有文件的解决方案
一个.NET Framework的Devexpress UI Windows Form项目,用的InstallShield,前些个版本都好好的,最近几个版本突然就没法更新了,每次更新的时候都覆盖不了原文件,而且这样更新后第一次打开程序(虽然是老程序&…...

服务器巡检表-监控指标
1、巡检指标 系统资源K8S集群NginxJAVA应用RabbitMQRedisPostgreSQLElasticsearchELK日志系统 2、巡检项 检查项目 检查指标 检查标准 系统资源 CPU 使用率 正常:<70% 低风险:≥ 70% 中风险:≥ 85% 高风险:≥ 9…...

无涯教程-JavaScript - DDB函数
描述 DDB函数使用双倍余额递减法或您指定的某些其他方法返回指定期间内资产的折旧。 语法 DDB (cost, salvage, life, period, [factor])争论 Argument描述Required/OptionalCostThe initial cost of the asset.RequiredSalvage 折旧结束时的价值(有时称为资产的残值)。 该…...
[2025CVPR]DeepVideo-R1:基于难度感知回归GRPO的视频强化微调框架详解
突破视频大语言模型推理瓶颈,在多个视频基准上实现SOTA性能 一、核心问题与创新亮点 1.1 GRPO在视频任务中的两大挑战 安全措施依赖问题 GRPO使用min和clip函数限制策略更新幅度,导致: 梯度抑制:当新旧策略差异过大时梯度消失收敛困难:策略无法充分优化# 传统GRPO的梯…...

1.3 VSCode安装与环境配置
进入网址Visual Studio Code - Code Editing. Redefined下载.deb文件,然后打开终端,进入下载文件夹,键入命令 sudo dpkg -i code_1.100.3-1748872405_amd64.deb 在终端键入命令code即启动vscode 需要安装插件列表 1.Chinese简化 2.ros …...
数据链路层的主要功能是什么
数据链路层(OSI模型第2层)的核心功能是在相邻网络节点(如交换机、主机)间提供可靠的数据帧传输服务,主要职责包括: 🔑 核心功能详解: 帧封装与解封装 封装: 将网络层下发…...
Spring Boot面试题精选汇总
🤟致敬读者 🟩感谢阅读🟦笑口常开🟪生日快乐⬛早点睡觉 📘博主相关 🟧博主信息🟨博客首页🟫专栏推荐🟥活动信息 文章目录 Spring Boot面试题精选汇总⚙️ **一、核心概…...
VTK如何让部分单位不可见
最近遇到一个需求,需要让一个vtkDataSet中的部分单元不可见,查阅了一些资料大概有以下几种方式 1.通过颜色映射表来进行,是最正规的做法 vtkNew<vtkLookupTable> lut; //值为0不显示,主要是最后一个参数,透明度…...

Ascend NPU上适配Step-Audio模型
1 概述 1.1 简述 Step-Audio 是业界首个集语音理解与生成控制一体化的产品级开源实时语音对话系统,支持多语言对话(如 中文,英文,日语),语音情感(如 开心,悲伤)&#x…...

MySQL 8.0 OCP 英文题库解析(十三)
Oracle 为庆祝 MySQL 30 周年,截止到 2025.07.31 之前。所有人均可以免费考取原价245美元的MySQL OCP 认证。 从今天开始,将英文题库免费公布出来,并进行解析,帮助大家在一个月之内轻松通过OCP认证。 本期公布试题111~120 试题1…...

GC1808高性能24位立体声音频ADC芯片解析
1. 芯片概述 GC1808是一款24位立体声音频模数转换器(ADC),支持8kHz~96kHz采样率,集成Δ-Σ调制器、数字抗混叠滤波器和高通滤波器,适用于高保真音频采集场景。 2. 核心特性 高精度:24位分辨率,…...

使用LangGraph和LangSmith构建多智能体人工智能系统
现在,通过组合几个较小的子智能体来创建一个强大的人工智能智能体正成为一种趋势。但这也带来了一些挑战,比如减少幻觉、管理对话流程、在测试期间留意智能体的工作方式、允许人工介入以及评估其性能。你需要进行大量的反复试验。 在这篇博客〔原作者&a…...

免费数学几何作图web平台
光锐软件免费数学工具,maths,数学制图,数学作图,几何作图,几何,AR开发,AR教育,增强现实,软件公司,XR,MR,VR,虚拟仿真,虚拟现实,混合现实,教育科技产品,职业模拟培训,高保真VR场景,结构互动课件,元宇宙http://xaglare.c…...