Facebook实习三面

楼主，你得出的这个复杂度和原题的4^n是一致的啊：你写的sum nCk*2^(k+1)，最后一个因子应该是2^k，因为你只考虑k个符号，插空分出来的第一个数是不带符号的。然后，sum nCk*2^k就等于3^n啊……这是二项式定理。

因为你这里没有乘法，所以有加、减、空3种情况，这样做也是3^n.

Spinoza 发表于 2017-12-11 12:21
楼主，你得出的这个复杂度和原题的4^n是一致的啊：你写的sum nCk*2^(k+1)，最后一个因子应该是2^k，因为你 ...

好像有道理……但是当时没答出来……听天由命了

感谢楼主分享 祝好运！