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 折旧结束时的价值(有时称为资产的残值)。 该…...
uniapp打包微信小程序。报错:https://api.weixin.qq.com 不在以下 request 合法域名列表
场景:在进行打包上传测试时,发现登录失效,但在测试中【勾选不效应合法域名】就可以。 出现原因:我在获取到用户code后,直接使用调用官方接口换取openid 解决方案: 可以把code带给后端,让他们返…...
stm32之31.iic
iic双线制。一根是SCL,作为时钟同步线;一根是SDA,作为数据传输线 SDN #include "iic.h"#define SCL PBout(8)#define SDA_W PBout(9) #define SDA_R PBin(9)void IIC_GPIOInit(void) {GPIO_InitTypeDef GPIO_InitStructure;//使能时钟GR…...
新的 ChatGPT 提示工程技术:程序模拟
即时工程的世界在各个层面上都令人着迷,并且不乏巧妙的方法来推动像 ChatGPT 这样的代理生成特定类型的响应。思想链 (CoT)、基于指令、N-shot、Few-shot 等技术,甚至奉承/角色分配等技巧都是充满提示的库背后的灵感,旨在满足各种需求。 在本文中,我将深入研究一项技术,据…...
【Python】爬虫基础
爬虫是一种模拟浏览器实现,用以抓取网站信息的程序或者脚本。常见的爬虫有三大类: 通用式爬虫:通用式爬虫用以爬取一整个网页的信息。 聚焦式爬虫:聚焦式爬虫可以在通用式爬虫爬取到的一整个网页的信息基础上只选取一部分所需的…...
leetcode分类刷题:队列(Queue)(三、优先队列用于归并排序)
1、当TopK问题出现在多个有序序列中时,就要用到归并排序的思想了 2、将优先队列初始化为添加多个有序序列的首元素的形式,再循环K次优先队列的出队和出队元素对应序列下个元素的入队,就能得到TopK的元素了 3、这些题目好像没有TopK 大用小顶堆…...
无线窨井水位监测仪|排水管网智慧窨井液位计安装案例
城市窨井在城市排水、雨水、污水输送等方面发挥着重要作用,是污水管网、排水管网 建设重要的组成部分。随着城镇精细化建设及人民安全防范措施水平的提高,对窨井内水位的监测提出了更高的要求,他是排水管网问题的晴雨表,窨井信息化…...
024 - STM32学习笔记 - 液晶屏控制(一) - LTDC与DMA2D初始
024- STM32学习笔记 - LTDC控制液晶屏 在学习如何控制液晶屏之前,先了解一下显示屏的分类,按照目前市场上存在的各种屏幕材质,主要分为CRT阴极射线管显示屏、LCD液晶显示屏、LED显示屏、OLED显示屏,在F429的开发板上,…...
Python数据容器:dict(字典、映射)
1、什么是字典 Python中的字典是通过key找到对应的Value(相当于现实生活中通过“字”找到“该字的含义” 我们前面所学习过的列表、元组、字符串以及集合都不能够提供通过某个东西找到其关联的东西的相关功能,字典可以。 例如 这里有一份成绩单…...
2023年基因编辑行业研究报告
第一章 行业发展概况 1.1 定义 基因编辑(Gene Editing),又称基因组编辑(Genome Editing)或基因组工程(Genome Engineering),是一项精确的科学技术,可以对含有遗传信息的…...
Spring MVC:请求转发与请求重定向
Spring MVC 请求转发请求重定向附 请求转发 转发( forward ),指服务器接收请求后,从一个资源跳转到另一个资源中。请求转发是一次请求,不会改变浏览器的请求地址。 简单示例: 1.通过 String 类型的返回值…...
商城类网站设计制作/搜索引擎优化技术有哪些
例如: JSON字符串:var str1 { "name": "cxh", "sex": "man" }; JSON对象:var obj { "name": "cxh", "sex": "man" }; 1、在js中把json字符串转json对象的方法不止一种࿰…...
网站建设九步走/百度竞价推广怎么做
9 为虚拟机启用容错在本节中,将把上一节安装配置的虚拟机启用FT(容错)功能。在启用容错功能之前,修改虚拟机的配置为2个CPU(2个插槽、每个插槽1个内核)、512MB内存。之后为虚拟机启用容错功能,主…...
做网站设分辨率/互联网营销培训课程
?? 点 击 上 方 蓝 字 关 注 我 ✿嗨,我是得闲 ?原本周末是要来更新职场穿搭的,发现有两套拍错了补拍了一下,正在重新修改,大概今晚或者明早就发布!自己总是跳票也真的非常非常不好意思,所以同时写了一个…...
网站开发人员如何写工作日志/有什么推广的平台
背景七年级数学上册第三章“一元一次方程”中,通过一些实际问题,研究了最基本的方程形式——一元一次方程,对求解一元一次方程采用了“去分母”、“去括号”、“移项”、“合并同类项”、“系数化1”等方法;学生在熟悉这些方法的同…...
网站建设怎么插图片/网站友情链接连接
2019独角兽企业重金招聘Python工程师标准>>> 最近在看TCP/IP详解卷1:协议 笔记好多地方懒得换成自己的话,直接COPY 看得有点手痒,想写一个远控来实现。 第一章 TCP/IP分为4个层次,应用层里的Telnet连接让我想起了 灰鸽…...
创新的网站建设公司排名/高级搜索百度
在web应用中,我们在web.xml配置URL路径问题时,经常这样配置: [html] view plaincopy print?<servlet-mapping> <servlet-name>spring-MVC</servlet-name> <url-pattern>/</url-pattern> </serv…...