取球游戏

在四面的时候最后被欢哥问到了一个很有趣的问题：有一个袋子里装了10颗球，分别标注上1～10，不放回的每次从袋子中取出一个球，并且要花6元的代价，但是可以获得摸到球的收益的值，例如摸到了7号球，就相当于赚了1元，玩家可以决定接着摸下去或者退出游戏，问怎么样决策才能让玩家赚钱。

可能是先入为主的思想，被欢哥问到这道题的时候，我当时脑袋里完全就把这个理解为一道数学概率题，想要试着去求解，但是后来发现解不了…就非常为难，然后欢哥当时简化到了三个球的情况，这个正常的数学期望还是算出来的，不过我当时仍然没有理解为什么欢哥说这是一道程序题，始终没有思路。结束后大概终于找到了思路，知道怎么去操作了，可惜终面的面试官不知道上个面试官问了什么问题。-v-。后来又跟逸凡聊了聊，就是一个树形dp+概率（唉，leetcode还是得再刷刷，不然碰到这类题根本联想不到啊）。

想法就是要构建一颗树，算出每一个决策后子树的数学期望，如果存在为正，则继续，否则就结束。关于子树的期望就用bottom-up的思路来求。简化问题为只有{5,6,7}三个球为例。如下示意图：

算出5子树的数学期望为0，6子树的为0，7子树的为1（因为7子树中，7的另外两个子树数学期望为0/-1，所以抽到7就选择结束，所以期望为1）。从而来决定最佳决策。非常有趣！