作者：梦露的殇_192 | 来源：互联网 | 2024-11-08 11:48
在网易2016年校园招聘笔试第二轮中，有一道题目涉及排列组合问题。题目描述如下：给定n个信封和n封信，要求将信重新放入信封中，但每封信都不能放回其原始的信封。请计算满足条件的不同放置方法的数量，并返回该数量对1000000007取模的结果。此问题可以通过递归或动态规划的方法高效求解。
有n个信封，包含n封信，现在把信拿出来，再装回去，要求每封信不能装回它原来的信封，问有多少种装法?
给定一个整数n，请返回装发个数，为了防止溢出，请返回结果Mod 1000000007的值。保证n的大小小于等于300。
测试样例：2 返回 1
一开始我以为是卡特兰数问题：卡特兰数应用
考虑半天，但是也无法列出卡特兰数的公式。安静下来发现，h(0)=h(1)=0，不满足卡特兰数条件。于是乎就想请教大神。大神给了个思路：
计算f(n),假设1,2,3,4,......n。那么n若放在位置i,可以分两种情况考虑。i放在位置n和i不放在位置n。为什么这么考虑呢？因为如果i放在n,那么剩下就是f(n-2),否则的话就是f(n-1)。第一种情况你很容易理解，i和n都放好了，剩下的就是n-2个数不放在原来的信封里。但是i如果不放在n位置，剩下n-1个数，其中i放哪都可以啊，和题目中每个信封不放在原信封条件不同啊。很好，i是可以放在任何位置，但前提假设了这种情况是i不放在n位置。这样这n-1个数，除了i,其余的限制是不放在原信封，i的限制是不放在n位置。所以等价这其实就是f(n-1)。
问题到这，用递归计算就太简单了。代码如下：
int countWays(int n) {
// write code here
if(n<2)return 0;
if(n==2)return 1;
return (n-1)*(countWays(n-1)%1000000007+countWays(n-2)%1000000007);
}
问题求得的结果没得问题，但是时间使用超过3000ms，远远超过限制时间。
但也可以猜想到，就是上述代码重复计算了太多值。于是乎，就改用循环。代码如下：
int countWays(int n) {
// write code here
int a=0;
int b=1;
if(n<=1)return a;
if(n==2)return b;
long result;
long x=0;
long y=1;
for(int i=3;i<=n;i++)
{
result=(i-1)*(x+y)%1000000007;
x=y;
y=result;
}
return result;
} 这样就很好了，根据n的大小，从头到尾计算一遍，直至f(n)。
总结：在一个序列上递归就很容易产生重复计算的问题，造成代码效率不高。同时一开始考虑问题总想着套路，这样并不好。有思路有解法才能利用公式等工具解决问题。先想解法，再看是不是公式，再解题。
京公网安备 11010802041100号