前两天看到一道小米的面试题

[mskf]

是这样的，如果你玩过 dota2 的话，很简单一句话，n 个球的卡尔有多少个技能

没玩过的话，大概介绍一下，卡尔有三个球，冰球 Q，雷球 W，火球 E，不同的组合对应不同的技能 QQQ （极冷）,QQW （峰哥漫步）,QQE （冰墙）,WWW （磁暴）,WWQ （吹风）,WWE （灵动迅捷）,EEQ （火人）,EEW （陨石）,EEE （天火）,QWE （推波）一共十个技能（不算天赋）

所以说如果卡尔有 4 个球，或者 n 个球，他会有几个技能呢

[lcatt]

高中排列组合。。。怎么可能有这么简单的面试题

[dinjufen]

玩过 dota2.试着答一下：
假如卡尔只能有三个框，n 个球（即一个技能含且只含三个球），那么他的技能数等于：
n （一个技能由同一种球构成，如 QQQ ） + 2n （一个技能由两种球构成，如 QQW ） + A3n （排列公式，一个技能由三种球构成，如 QWE ）

当然有另一种情况就是有 n 个球，并且有 n 个框：
结果应该是 C1n + C2n + ... + Cnn （组合公式）

若有问题，欢迎指出。。。

[mskf]

@dinjufen 一种组合有不同的排列方式，比如 n=4，C2,4=6 但这六种组合每种对应的技能并不止一种：
QQWW,QQQW,WWWQ 这就三种了

[codeless]

emm，想象了一下 n （ n>104 ）个键的键盘。。。

[coderluan]

这题肯定是高中数学题，但是如果你想到的是高中算法，而不是递归树或者二进制的话，对程序员来说，这题你就算不回。

[dinjufen]

@mskf 嗯，是的

[yhxx]

@mskf 可是 WWQ 和 QWW 确实是同一个技能啊（逃

[calpes]

@coderluan 这是什么说法。。。有更高级的数学证明不能用还非得用递归了？

[WuwuGin]

我就提醒一句组合相同排列不同算同一种技能哦。

[binux]

看回复这题还真的能筛选候选人

[mskf]

@coderluan 我一开始也是这么想的，想了好久硬是没有想到怎么用 dp 做，后来尝试了一下用纯数学，很简单就搞定了

[zxcvsh]

10 楼 结贴

[coderluan]

@calpes

第一，你要理解面试官的意图，你认为对方是想考你高中数学，还是更想考你编程技巧？
第二，算法很大程度是在解决数学的性能问题，相辅相成的东西，何来的”更高级“？，你随便找一个常用的库，你看看里面的实现是用算法，还是用公式？

[mxalbert1996]

@coderluan 我觉得你根本就没理解算法是个什么东西。

[coderluan]

PS：有兴趣的同学，可以看看 STL 里面的 permutation 实现，按这个答基本大部分面试官自己就跪了。

[batman2010]

@coderluan #13 用排列组合的方法也只是用到简单的乘除法。

[nazor]

1*n + 2*(n-1) + 3*(n-2) + ... + n*1

[coderluan]

@mxalbert1996

我只是表面自己观点，给出自己的证据，如果你认为有问题，也可以表面观点和证据，然后咱们交流和讨论。但是你发的这句话，我只能说我觉你根本没理解沟通是个什么东西。

[blackjar]

就是重复组合啊

[1KN6sAqR0a57no6s]

想起了七年前的夏天我在家里的凉席上用纸笔算卡尔有多少技能。

[CastleBUPT]

是从 n 个球选 3 个排技能吗，是的话，C1n + 2*C2n + C3n

[binux]

@mskf #11 dp 就是 f = lambda m, n: sum(f(i+1, n-1) for i in range(m)) if n > 1 else m

[chenno9]

f(4)=c(1,4)*c(3,3)+c(2,4)*c(2,3)+c(3,4)*c(1,3)+c(4,4)*c(0,3)=35

f(n)=c(1,n)*c(n-1,n-1)+c(2,n)*c(n-2,n-1)+c(3,n)*c(n-3,n-1)+...+c(n,n)*c(n-n,n-1)

[calpes]

@coderluan 不是这个说法吧。。。很多库的实现里都直接用了 magic number，这显然是数学范围的优化啊，在有更高级数学模型的情况下还强行上递归，这并不是明智的行为，你不能因为通常情况下可能找不到更简洁的数学模型，就在能找到的时候不用啊，更何况大多数情况下只是由于工程师的数学水平不够，而不是没有相关的数学模型。

[Nathanzheng]

rua?

[mscststs]

算法不就是为了更高效地解决问题吗？递归全排有数学公式来得高效？

[calpes]

@coderluan 就比如一个穷举素数的算法，一般来说实现中对素数的判断条件都是如果除数大于结果就认为这是一个素数，这明显是数学理论的支持啊

[lychnis]

只算个数还是输出所有 这可不一样

[shyrock]

说实话题没理解清楚，为啥 3 个球只有 10 种技能？ EWQ 这种为啥没有？

[polo3584]

@shyrock EWQ 就是 QWE，这个不算排序的

[coderluan]

@calpes 我说那个只是反驳数学证明就高级，实际上哪个性能好用哪个，随便找个库肯定也有公式的，这个点我不严谨。而且我也并没有强行上递归，而是说面试程序员出这题，面试官应该是想要递归之类的算法相关的回答，而不是高中数学。

[mskf]

@chenno9 正解，f(x)=∑C(i,x)*C(i-1,x-1)(0<i<x)

这题用 dp 做简直没法做，偏偏还挺容易想歪的

[mskf]

@shyrock EWQ=QWE，如果不考虑顺序的话就太简单了，直接 n^n

[mskf]

@lychnis 只算个数

[mskf]

@Nathanzheng rua

[mskf]

@mscststs 这题如果想用数学公式以外的方式去解决，很容易想歪，如果现场写代码的话排列组合的优化还是有地方可以写的

[maswang]

我不知道是多少，但是我知道怎么写个程序帮我算出来

[lxy42]

数学推导公式：
f(n) = 1 + n * [C(1, n-1) + C(2, n-1) + ... + C(n-1, n-1)]

f(3) = 1 + 3 * [C(1, 2) + C(2, 2)] = 1 + 3 * [2 + 1] = 10
f(4) = 1 + 4 * [C(1, 3) + C(2, 3) + C(3, 3)] = 1 + 4 * [3 + 3 + 1] = 29

[lostberryzz]

肯定是推公式效率高啊。。

[mandy0119]

1234 => 0 空位，1 空位（ 2 种球），2 空位（ 2 种球），3 空位（ 2 种球） 。虽然规律出来了，但是我没总结出来公式

[jetyang]

说写程序的可以歇歇了，这是笔试里的一道选择题。正解 @chenno9 已经给出来了，当然还有更简洁的通项表达，多看看组合数学和概率论呗

[Ncanback]

排列组合的典型 为什么会想到用回调递归？

[tohert]

我怎么想到的是笛卡尔乘积。。。

[Arxz]

只会用 dp...排列组合想了半天没想出来

[justfan]

```
#include "stdio.h"
void main()
{
char a[3] = {'q', 'w', 'e'};
int i,j,k;
char tmp1, tmp2, tmp3;
for(i=0;i<3;i++)
{
tmp1 = a[i];
for(j=i;j<3;j++)
{
tmp2 = a[j];
for(k=j;k<3;k++)
{
tmp3 = a[k];
printf("%c%c%c\n", tmp1, tmp2, tmp3);
}
}
}
}
```

[mskf]

@justfan 3^3=27>10，所以有重复的，面试题一般不会考这么简单的三重循环

[lxy42]

python 的一个解法：

https://gist.github.com/ausaki/4219b54eb54654216008103c30d93f72

[justfan]

@mskf 不是三重循环 for(j=i;j<3;j++) for(k=j;k<3;k++)

[NBGGA]

你以为他们想考你算法，其实他们只想招个 DotAer🤣

[across]

https://leetcode-cn.com/problems/combinations/

[across]

@across 啊，我忘了，卡尔技能是没有顺序关系的

[isaacpei]

居然没人发 oeis??? 我来补上 http://oeis.org/A001700

[Vitta]

1 技能加攻击，2 技能加速度，3 技能加回血

[VoidChen]

那啥，我没玩过 dota，但是我看你们的描述，你们可能搞错了一点东西，n 个球，有没有限制球能不能重复用，另外就是 n 个球都是什么球，比如 n 个都是冰球，当 n > 2 的时候 1 个技能。我觉得这道题有点问题吧，跟 N 的关系好像就只是是不是＞ 2 了？

[VoidChen]

@VoidChen 或者说 n/3 个技能。。。。。。。。

[VoidChen]

不好意思，，就是排列组合。。我把这道题的意思想成 LOL 的波珠妹了，以为一共就 3 种球。。。。。

[ccpp132]

n 种球每次 m 个就是 C(n + m -1, n)....
高中组合数学知识其实够用了
相当于 x1 + x2 + ... + xn = m 的正整数解的个数，把 m - 1 个隔板和 n 个球放到一起排

[ccpp132]

@mskf @chenno9 帮你们化简了，比较好手算，滑稽

[VagrantSven]

7C3=35，七个球涂黑三个球当分割

[Ginray]

@chenno9 请问 c(n-n,n-1) 这个是代表什么意思，谢谢

[SakuraKuma]

#57+1
H(n,n)..

[zqx]

像是 100 只老鼠用最少几次可以试出毒的那个题吧？二进制串来表示，最后取并集？

[Rhonin]

@NBGGA #49 你这才是正解哈哈哈

[zzzzzzZ]

@coderluan #13
面试官的意图这一道题我是没看出来，但是做道题都舔的面试者的意图我看得很明显

是闹哪样，立直要当上面试王的男人吗

[chenno9]

@Ginray n 种颜色的取法*这 n 种颜色的组合 我这里写反了 应该是 32 楼的公式

[linchengzzz]

23 正解 啊 , 我不信还手算了一遍

[a728976009]

https://baike.baidu.com/item/%E9%87%8D%E5%A4%8D%E7%BB%84%E5%90%88/6774375

[jk1030]

你们啊 naive 点完天赋还有一个毁天灭地 这个东西考察得不是算法 而且对公司产品得服从度

[KevinBu]

python 两行代码搞定 🤩

for i in itertools.permutations('qwer', 4):
print(''.join(i))

[mskf]

@justfan 哦哦，不好意思没注意，感谢你给了我一点启发，不使用递归也是可以实现的：
```java
public int solution2(int n){
int res = 0;
int x=n-1,y=0,level = 0;
int prev[] = new int[n];
while (true){
if(x==0 && y==n) {
prev[x] = ++level;
if (level==n) break;
} else if(x<n-1) {
if(y==n)
y=++prev[--x];
else {prev[x+1] = prev[x];x++;}
} else if(x==n-1) {
res++;
if(y<n-1) y++;
else y=++prev[--x];
}
}
return res;
}
```

[newtype0092]

@coderluan 算法题不懂数学原理，只会用数据结构低效的模拟，难道不是水平 low 的表现么？程序员思维是用高效的方法解决问题，而不是只会用固定的套路。。。

[JohnSmith]

@KevinBu #69 你这个完美的把有重复部分的技能去掉了，e.g. wwww

[JohnSmith]

@KevinBu #69 还把同样字母的不同顺序的也算进去了

[HeavenlyChorus]

只想说一句 r-combination 的 r 应该是写在后面的，如此:C(n,r),楼上几位都写反了

[choice4]

@linchengzzz 你这个等号是什么科技？

[JohnSmith]

n = 球种类 k = 组合长度
C(n,1)+c(n,2)+...+c(n,k)

[liyuhang]

@choice4 #75 https://github.com/tonsky/FiraCode

[jiajia94]

别问，问就是高等级天火

[coderluan]

@newtype0092 我说的是只是高中水平的数学是没办法让面试官满意的，你怎么推理出“不懂数学原理，只会数据结构”的 ？ 喵喵喵 ？

[linchengzzz]

@choice4 FiraCode 字体

[trcnkq]

(n+2)*(n+1)/2

[jin5354]

f(n) = C(n-1, 2n-1)
查了下资料，这种解法真是太巧了，f(4) = C(3, 7) = 35

[siyemiaokube]

高中 oi 选手让各位再感受一些压力吧(◐‿◑)
上面说到的 C(n-1, 2n-1)，其实可以再展开说好多，不妨从“生成函数”入手查一些资料

[siyemiaokube]

@HeavenlyChorus
>只想说一句 r-combination 的 r 应该是写在后面的，如此:C(n,r),楼上几位都写反了

“ C ”这种苏式组合数记法，一般默认上标在前下标在后。美式的括号记法，确实是(n,r)

[staticer]


[HeavenlyChorus]

@siyemiaokube 学习了 我学校教的是我说的那样

[atVoid]

有放回组合问题，推导挺有意思的。https://zhuanlan.zhihu.com/p/33841038 C(n+m-1,n-1) n 个球 m 个框(盒子)

[NullPoint]

没太懂，QQE EQQ QEQ EEQ EQE QEE，算俩技能

[whi147]

(r+n-1)!/r!(n-1)! r=4 n=4

[seraphv3]

有 3 个按键，QWE，需要按 3 次，相当于把 3 个球（ 3 次按键的动作）放到 3 个盒子（ QWE ）中，找出可区分的排布数。
3 个盒子有 2 个隔板，这 2 个隔板和 3 个球一起就有 5 个位置，5 个位置中任选 2 个放隔板，其他的就是球，所以就是 C(2,5)
Q W E
|x |x |x |
|xx |x | |
|x |xx | |
...
|xxx| | |
| |xxx| |


PS:盒子中放球的模型不像想象的那么简单，统计力学里面有 Maxwell-Boltzmann 统计（比如气体分子）、Fermi-Dirac 统计（比如电子）、Bose-Einstein 统计（比如光子），用这道题的统计方式来统计样本空间（不同的排布是可区分的）就对应于 Bose-Einstein 统计，有一个简单的 Polya ’ s urn model 可以实现它

[calpes]

@coderluan 其实我是这么理解的，一定的数学基础是合格程序员的先决条件，如果你没有高中水平的数学知识，你根本不可能是一个合格的程序员，如果我是面试官(事实上我确实是)，我一定不会给一个没有数学常识的人任何机会。

[mxalbert1996]

@coderluan 因为你让我觉得没有跟你沟通的必要。一个对算法稍微有点理解的人也至少不会把算法和公式对立起来。

[laydown]

如果 4 个球的话，按 1 个键就是 4 种，按 2 个键，就是 10 种，按 3 个键就是 20 种，按 4 个键就是 35 种，合起来就是 4+10+20+35，共 69 种。

重复组合的概念。

[ihciah]

卡特兰数？

[mingl0280]

@lxy42 O(n^4)的算法和数学的 O(1)的算法，是正常人都知道该用啥……

[mingl0280]

@coderluan 这道题只需要高中水平的数学知识，如果你连这点知识都没有，最好别称自己为程序员，笑掉大牙的。

[Variazioni]

这年头没玩过 dota2 都不能去小米了？

[graysheeep]

qqwrv

[coderluan]

@calpes 是啊，所以我说的一直都加上了， “更” “不能满足”“没谁高级”“相辅相成” ，不知道你们咋理解的成我吹算法捧数学的。

[coderluan]

@mxalbert1996 是有人先说的数学更高级，我反驳他时明确用了“相辅相成的东西，何来的”更高级“？”#13

你还能理解成我把“算法和公式对立”。我也不知道咋和你沟通了。再送你句 “我只能说我觉你根本没理解语文是个什么东西”。