《飞镖王》是休闲小游戏大集合pk32里的小游戏之一，作者本意想模拟的是飞镖运动，但由于这项运动相比台球而言，较难复刻在PC/安卓等虚拟平台，实际效果可玩性在整套合集里也比较一般。下面是这个游戏的界面：

游戏要求在给定机会内将分数清零，并且要求目标数字必须都被射中。初级难度有24次机会，2个目标数字，中级难度18次机会，3个目标数字，高级难度只有12次机会，但要求射中多达4个目标数字。各个级别初始分数均为501。飞镖盘上共有从1~20的20个数字，每个数字都有单倍，双倍和三倍区，射中对应区域则分数可以乘2或者乘3。正中央有单倍红心区和双倍红心区，pk32复刻版单倍红心区为50分，双倍红心区为100分，相比普通飞镖运动翻倍了，这样对玩家更为友好，一般情况下尽量瞄准中心就可以尽快降低剩余分数。如果剩余分数小于射中的分数，那么剩余分数不变，但是如果射中的是目标数字，那也算有效。

这样显然高级难度一定有解，而且至少能剩余2次机会。一个平凡解是这样，前5次都射双倍红心区，分数就只剩下1，接下来4次射4个目标数字（这时分数不变），如果目标数字不包括1，那么再射1次数字1的单倍区，这样保证可以9~10次完成任务。

(资料图片)

UP的个人纪录是中级剩余9次机会，高级剩余2次机会。那么过关后剩余机会的理论上限应该是多少呢？本专栏就讨论这个问题。

这个问题看似可以贪心求解，实则不然。不难发现可以单次射中的分数不是连续的，如57和60之间，60和100之间没有其他的单次有效射中分数。另外目标数字是必须要射中的，但并不一定都射3倍区是最优的，这是因为分数需要恰好归零，不能成为负数。

实际上可以用背包型动态规划的方法求解，如果没有目标数字，就可以用dp[left]表示剩余分数left时清空分数需要射的最少次数。由于每个目标数字是否被射过是独立的，可以用位掩码的形式表示，即mask的第j位为1，表示tgt[j]已被射过，tgt为目标数字构成的数组。如掩码1110，表示4个目标数字里，只有最小的一个没被射过。因此最终状态定义为dp[left][mask]表示剩余分数left，各个目标数字的被射中情况为mask时，清空分数并射完目标数字所需要射的最少次数。以高级为例，边界条件为dp[0][0b1111]=0，dp[0][mask]=∞（mask为非全1的掩码）。我们想要求的实际就是dp[501][0]。

由于状态定义较为复杂，可以模拟游戏过程，用递归形式即记忆化搜索，来实现动态规划。Python语言可以使用functools的cache自动记忆化，其他语言使用二维数组来手动记忆化。由于每次可以射任意数字的单倍双倍三倍区，以及单倍和双倍红心区，共62个区域，因此每个当前状态最多对应62个新状态。但并不是所有操作都有效，使用记忆化搜索时，如果做无效操作，就会让程序陷入死循环，无法求解。有效操作需要满足下列条件之一：

1. 当前操作可以降低分数

2. 当前操作虽然不能降低分数，但可以改变掩码

当然，操作1也有可能改变掩码，因此需要在记忆化搜索前对每个数字对应的掩码先做预处理，模拟操作过程时，无论作何操作，下一个状态的掩码，都应该是当前状态掩码与当前射的数字的掩码做一个按位或操作。

这就是记忆化搜索部分的Python代码。

如何分析复杂度呢？设n为目标数字的数量，m为游戏盘面最大数字，C为需要清零总分，显然共有C*2^n个状态。每个状态的处理需要模拟所有可能的操作，对这个问题是3m+2个，即O(m)的，因此总时间复杂度就是O(C*2^n*m)。对于C=501，n<=4，m=20，总复杂度小于6个数量级，因此计算单次游戏的max是极为快速的。

如果想要计算所有可能的目标数字里的最不利情况呢？可以用LeetCode主站第77题的枚举组合的方法，枚举所有可能的目标数字组合，然后分别计算。事实上由于最多只有4个目标数字，完全可以暴力4个for循环，时间复杂度也不会提升。

上面的代码为枚举组合的方法，对于这个场景其实是不必需的。

作者给出计算结果：

对于初级而言，共有C(20,2)=190种组合，其中148种可以射7镖完成，剩余42种均可以射8镖完成，也就是过关剩余次数的max近80%的概率为17，其余情况为16。

对于中级而言，共有C(20,3)=1140种组合，其中946种可以射8镖完成，176种则需要射9镖，还有18种理论只需要7镖。也就是过关剩余次数的max，约5/6的情况为10，近1/6的情况为9，还有极低概率为11。

对于高级而言，共有从C(20,4)=4845种组合，其中3169种可以射8镖完成，1662种需要射9镖，理论上射7镖能完成的有13种组合，还有一个最特殊的组合：[2,3,4,5]，这时候射10镖的平凡解就已经最优了，其实[2,3,4,5]没有更好的解法，多想一想还是不难证明的，但UP在运行这个代码前，一直认为至少要射10镖的目标数字组合未必存在。因此，高级难度过关剩余次数的max，近2/3的情况为4，超1/3的情况为3，极低概率为5，如果碰到了最非酋的组合，max只有2。