LeetCode 634. 寻找数组的错位排列(DP)
发布日期:2021-07-01 03:30:06
浏览次数:2
分类:技术文章
本文共 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 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
能坚持,总会有不一样的收获!
[***.219.124.196]2024年04月09日 11时52分21秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
启用fcitx-qimpanel面板程序
2019-05-03
浅谈Q的基本实现
2019-05-03
iOS开发——cache自动清理方案探索
2019-05-03
阿里云短信服务(JAVA)
2019-05-03
std::exception标准和各平台实现的不同
2019-05-03
C++的匿名对象
2019-05-03
C++中class和typename的区别
2019-05-03
C++常量表达式、const、constexpr(C++11新增)的区别
2019-05-03
Windows和Linux进程与线程的区别
2019-05-03
Windows下C++多线程编程(入门实例)
2019-05-03
宽字符标量L"xx"在VC6.0/7.0和GNU g++中的不同实现。
2019-05-03
VS工程属性“字符集”和源文件“高级保存选项”字符集区别
2019-05-03
Linux下C++多线程编程(入门实例)
2019-05-03
深入理解HashMap
2019-05-03
[arr firstObject] 和 arr[0] 的区别
2019-05-03
求解最大子列和问题——MaxSubSum
2019-05-03
iOS9新特性之常见关键字
2019-05-03
iOS中 单例设计模式 的使用方法
2019-05-03
GCD使用 串行并行队列 与 同步异步执行的各种组合 及要点分析
2019-05-03
iOS开发------程序实现国际化Localizable
2019-05-03