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

题目都看不太懂的路过

brn 发表于 2017-8-3 09:56
怎么定义状态？怎么转移？

6维dp（感觉应该根据剩余牌数等等的关系可以简化到5维左右，懒得想了）

opt[#remaining cards][current player][player1 hand][player2 hand][player3 hand][player4 hand] = max(opt[#remaining cards - 1][current][p1][p2][p3][p4], opt[#remaining cards - 1][next player][p1][p2][p3][p4])

大概就是这样，刚才翻了一下，其实楼上有人说过了。

时间"复杂度"还好，52*4*21^4种状态，算个几秒钟就出来了。
(想了一下，漏了一点：）

略微tricky的是player hand的状态，因为可以有1个到4个Ace。这里其实也简单，在发牌的时候我们就可以决定这张Ace是当1还是10，然后转移方程里面多加上一个状态即可。