LeetCode 634. 寻找数组的错位排列(DP)
发布日期:2021-07-01 03:30:06
浏览次数:3
分类:技术文章
本文共 912 字,大约阅读时间需要 3 分钟。
文章目录
1. 题目
在组合数学中,如果一个排列中所有元素都不在原先的位置上,那么这个排列就被称为错位排列。
给定一个从 1 到 n 升序排列的数组,你可以计算出总共有多少个不同的错位排列吗?
由于答案可能非常大,你只需要将答案对 109+7 取余输出即可。
样例 1:输入: 3输出: 2解释: 原始的数组为 [1,2,3]。两个错位排列的数组为 [2,3,1] 和 [3,1,2]。 注释:n 的范围是 [1, 106]。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/find-the-derangement-of-an-array 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
2. 解题
class Solution { //C++public: int findDerangement(int n) { if(n==1) return 0; vectordp(n+1, 0); dp[0] = 1; dp[1] = 0; for(int i = 2; i <= n; ++i) dp[i] = ((i-1)*(dp[i-1]+dp[i-2]))%1000000007; return dp[n]; }};
class Solution: #py3 def findDerangement(self, n: int) -> int: if n==1: return 0 dp = [0]*(n+1) dp[0] = 1 dp[1] = 0 for i in range(2,n+1): dp[i] = ((i-1)*(dp[i-1]+dp[i-2]))%1000000007 return dp[n]
我的CSDN
长按或扫码关注我的公众号(Michael阿明),一起加油、一起学习进步!
转载地址:https://michael.blog.csdn.net/article/details/107577515 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
留言是一种美德,欢迎回访!
[***.207.175.100]2024年04月18日 00时39分46秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
java.net.BindException: 无法指定被请求的地址
2019-05-01
svn服务器安装
2019-05-01
spark 笔记1
2019-05-01
shell dirname basename
2019-05-01
未来已至,5G加持下的云游戏将走向何方?
2019-05-01
计算机网络 —— 网络层 1.
2019-05-01
Android 之 ContentProvider 与 ContentResolver
2019-05-01
【接口自动化】
2019-05-01
Python解惑之:True与False
2019-05-01
你要的微信小程序终于来了
2019-05-01
有了这些 Chrome 插件,效率提升10倍(建议收藏)
2019-05-01
只有1%的程序员搞懂过浮点数陷阱
2019-05-01
一名 Google 工程师的大数据处理经验
2019-05-01
命名难,难于上青天
2019-05-01
没钱没公司,怎么做一款付费产品
2019-05-01
代码整洁之道-编写 Pythonic 代码
2019-05-01
树莓派程序开机自启动
2019-05-01
连锁门店无线通信方案
2019-05-01
配置Lotus Domino集群视频详解
2019-05-01