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

[mskf]

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

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

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

[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 种球） 。虽然规律出来了，但是我没总结出来公式