2018年奇虎360春招笔试题--玫瑰花
这道题，第一感觉想用排列组合做，但是想了好久，没想到解决办法（刚刚考试的时候没有答出来）。后来想了一下应该使用动态规划来做。
我们首先分析一下情况：
1.当K>N的时候，countSum = 0；
2.当K=N的时候，countSum = N！（N的阶乘）
3.当K>N的时候，就要通过最优子结构来进行分析了。
前两点易知，下面主要分析第三点。
设F(k,n)为n个位置，k种玫瑰的结果，则 F(k,n) = k*(F(k,n-1)+F(k-1,n-1))，分析：
情况一：n-1个空缺已经放置了k种花，则新的位置放置任何一种花都可以，此时结果总数为k*F(k,n-1)；
情况二：n-1个空缺已经放置了k-1种花（注意！有k种选择！），则新的位置固定需要放置剩下的那一种花，此时结果总数为k*F(k-1,n-1)；
总数 = 情况一 + 情况二
代码如下：
public class Rose {
public static void main(String[] args){
System.out.println(roseSum(2,3));
}
public static long roseSum(int k,int n){
if(k>n) return 0;
if(k == n){
int count = 1;
for(int i = 0;i<n;i++)
count*=i;
return count;
}
long[][] DP = new long[k][n];
for(int i = 0 ;i<n;i++)
DP[0][i] = 1;
for(int i = 1;i<k;i++)
DP[i][0] = 0;
for(int i = 1;i<k;i++)
for(int j = 1;j<n;j++)
DP[i][j] = (i+1)*(DP[i][j-1]+DP[i-1][j-1]);
return DP[k-1][n-1]%772235;
}
}不过此代码虽然是使用动态规划解决，但是空间复杂度为O(N*K)，并不是最优，还可继续优化。
优化代码如下：
public class Rose {
public static void main(String[] args){
System.out.println(roseSum(2,3));
}
public static long roseSum(int k,int n){
if(k > n) return 0;
if(k == n){
int count = 1;
for(int i = 0;i<n;i++)
count*=i;
return count;
}
long[][] DP = new long[2][n];
for(int i = 0 ;i<n;i++)
DP[0][i] = 1;
DP[1][0] = 0;
for(int i = 1;i<k;i++)
for(int j = 1;j<n;j++)
if((i&1)==1){//此时i是奇数
DP[1][j] = (i+1)*(DP[1][j-1]+DP[0][j-1]);
}else{
DP[0][j] = (i+1)*(DP[0][j-1]+DP[1][j-1]);
}
return DP[(k-1)&1][n-1]%772235;
}
}这回的空间复杂度为O(N)。
自己想出来的，不一定准确，没经过大量试验，如有错误，请各位朋友指出，谢谢~
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2018-04-03 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读