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

[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]

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