这个算法面试题没有做出来，刷了那么久的题，面试死在这题上了

shuyangsheng 发表于 2017-5-18 11:23
一路在潜水。。。这个解法是对的，但是复杂度有点高。简化问题是一个二维DP，复杂度是21*v， 然后要考虑n ...

诶嘿嘿，我知道解法复杂度很高，所以抛砖引玉嘛，希望有人能提出更优化的算法。
另外，终于有人回复我了，我好高兴啊。

那楼主这里A怎么算？什么时候当1，什么时候当11？

比如5 6 A，A就只能当1，继续等下面的牌
5 5 A, A应该当11
5 4 A, A两种情况都可以，在我们没有看到后面牌的情况下没法决定？
我的理解对吗？

zzwcsong 发表于 2017-5-18 11:25
把52张牌分给4个人，共有C(52, 4)种分法，所以按层主你的这个解法需要遍历这每种分法的组合喽？对给定的 ...

啊不对啊好像远不止C(52,4)种组合，没有规定只能按顺序把牌切成四份，完全可以先给A发一张再给B发一张然后再给A发一张这样。总共是5^52种组合（每张牌都可能发给任意一个人或者弃掉）。

zzwcsong 发表于 2017-5-18 11:25
把52张牌分给4个人，共有C(52, 4)种分法，所以按层主你的这个解法需要遍历这每种分法的组合喽？对给定的 ...

确实实际上是遍历了每种分发的组合，所以时间复杂度很高。不过这部分用动规来做实际会出现很多重复的情况，如果可以记录下中间结果就能减少一些重复的计算，不过空间复杂度会提升，算是牺牲空间换时间吧。

shuyangsheng 发表于 2017-5-18 11:32
啊不对啊好像远不止C(52,4)种组合，没有规定只能按顺序把牌切成四份，完全可以先给A发一张再给B发一张然 ...

没错，是你说的那么多种组合，所以这是一个np问题。

zzwcsong 发表于 2017-5-18 11:30
那楼主这里A怎么算？什么时候当1，什么时候当11？

比如5 6 A，A就只能当1，继续等下面的牌

你看一下我前面发的getN代码就知道这种情况要怎么办了。实际上不需要知道，只要把A当做A（我在代码里记为1，这样比较好写），然后发牌后，直接计算一人情况下的最优解就好。

shuyangsheng 发表于 2017-5-18 11:32
啊不对啊好像远不止C(52,4)种组合，没有规定只能按顺序把牌切成四份，完全可以先给A发一张再给B发一张然 ...

啊~确实所有的分法组合C(52, 4)是不对的，5^52好像是对的，我再想想

不过如果考虑到分解为4个单人问题，每个单人问题是可以解决弃牌问题的，那么弃牌分到4人中的任意一人似乎都可以。

顺便一说，我没有系统的学过计算复杂度，所以如果有人愿意帮忙计算一下楼上那个算法的（时间、空间）复杂度我会非常感谢哦！

我打算读研究生的时候系统的学一下。

提供一个思路，虽然所有的分牌组合有5^52次方种，但其中有许多序列是不合法的。所以可以用backtrack来穷举所有合法的可能。

给定一个牌组，A 4 5 3 9 A 10 10
对于任意一个给定分牌序列，比如
A  B # C # D # A
我们是能计算出它是否valid， 如果valid，生成21点的次数的。

那么我们backtrack的流程就是：
1. 从头开始产生所有可能的发牌序列，
2. 如果此时添加的某张牌使序列invalid，那么我们把这张牌用弃牌代替
3. 递归尝试把下一张牌发给ABCD#中的一个，#代表弃牌
4. 如果我们发了52张牌，那么我们记录当前获得21点的次数，并更新最大21点次数
5. 返回最大21点的次数

zzwcsong 发表于 2017-5-18 12:07
提供一个思路，虽然所有的分牌组合有5^52次方种，但其中有许多序列是不合法的。所以可以用backtrack来穷举 ...

不过52张太多了...暴力法应该是跑不完的