提问人：Maxime B 提问时间：3/16/2021 最后编辑：Maxime B 更新时间：3/17/2021 访问量：67
查找特定结果的 n 个间距操作的组合
Finding the combinations of n-spaced actions to a specific result
问：
鉴于以下陈述：
2名玩家每人有100HP值
它们都可以使用 -2HP、-5HP 或 -7HP 攻击进行攻击
他们可以连续无限次攻击
当玩家的HP为<= 0时，玩家就输了
我需要找到玩家 A 战胜玩家 B 的情况数量。
这是我到目前为止的代码：
import itertools
win = 0
for j in itertools.product(range(1, 7), repeat=100):
a = 100
b = 100
for i in j:
if (i == 1):
b -= 2
elif (i == 2):
b -= 5
elif (i == 3):
b -= 7
elif (i == 4):
a -= 2
elif (i == 5):
a -= 5
elif (i == 6):
a -= 7
if b <= 0 and a > 0:
win += 1
if (win % 1000000 == 0):
print(j)
print(win)
break
if a <= 0:
break
我选择了 100 次重复，以应对玩家 A 和 B 都只用 2HP 攻击的极端情况。
当然，这将花费大量时间来计算。
我需要找到一个更快的算法。
答：
1赞
Dave
3/17/2021
#1
首先使用 DP 填充矩阵 s.t. 位置 （i，j） 中的值表示在 j 步中失去 i 生命值的方式计数
arr[i，j] = arr[i-2， j-1] + arr[i-5， j-1] + arr[i-7， j-2]，只考虑先前的非获胜值（所以我在先前的值中< 100）。
初始化 arr[0,0] = 1
我们将按照 j 和 i 的递增顺序填充它，从 j=1 开始
i >= 100 时，索引 （i， j） 处的值表示在 j 步中获得获胜分数的方法计数。这将上升到 106，这是最高获胜分数 （99+7）。同样，对于 i < 100，这些表示在 j 步中获得失败分数的方法计数。
对于每一步棋，计算在那么多步数中获胜和失败的方式数量。我们将能够在 0-49 步中输掉，并能够在 15-50 步中获胜。
现在，对于每个获胜的分数，对于每个失败的分数，我们需要计算这些计数可以交错的方式。假设我们在 j 步中获胜，在 k 步中输掉分数。这就是 choose（j + k - 1， k）。
-1 是因为最后一步（获胜的一步）必须来自获胜的集合。可以把它看作是从 j+k-1 可能性中选择失败步数的 k 个位置，以涵盖以获胜步数结束的所有安排。
最终答案：对于在 j 步中获胜和在 k 步中输掉的每种方式，我们将 （j-move 获胜次数） * （k-move 损失次数） * choose（j+k-1， k） 添加到我们的总数中。
例如，最大生命值为 10 的矩阵和胜/负小计：
> count_wins([2,5,7], 10)
hp loss: 0 1| 0| 0| 0| 0| 0|
hp loss: 1 0| 0| 0| 0| 0| 0|
hp loss: 2 0| 1| 0| 0| 0| 0|
hp loss: 3 0| 0| 0| 0| 0| 0|
hp loss: 4 0| 0| 1| 0| 0| 0|
hp loss: 5 0| 1| 0| 0| 0| 0|
hp loss: 6 0| 0| 0| 1| 0| 0|
hp loss: 7 0| 1| 2| 0| 0| 0|
hp loss: 8 0| 0| 0| 0| 1| 0|
hp loss: 9 0| 0| 2| 3| 0| 0|
hp loss: 10 0| 0| 1| 0| 0| 1|
hp loss: 11 0| 0| 0| 3| 4| 0|
hp loss: 12 0| 0| 2| 2| 0| 0|
hp loss: 13 0| 0| 0| 0| 1| 1|
hp loss: 14 0| 0| 1| 4| 3| 0|
hp loss: 15 0| 0| 0| 0| 0| 1|
hp loss: 16 0| 0| 0| 2| 3| 0|
loss: 1| 3| 5| 4| 1| 0|
win: 0| 0| 4| 11| 11| 3|
=> 4078 (ways of winning)
对于 3 的最大 hp，我得到：
count_wins([2,5,7], 3)
loss: 1| 1| 0|
win: 0| 2| 3|
=> 13 (ways of winning)
A 获胜的 13 种方式。这些是：
A's moves: [[5], [7], [2,2], [2,5], [2,7]]
B's moves: [[], [2]]
A 获胜的 5 种方式中的每一种都可以是没有 B 步 （5）、单个初始 B 步 （5），或者在 3 种情况下，在两个 A 步之间只有一个 B 步 （3）。根据上述算法，我们的总数为 13。
对于count_wins（[2,5,7]， 100），我得到的最终答案是：
102,033,940,458,046,779,283,026,415,918,520,992,505,663
评论
0赞
Dave
3/17/2021
通过哈希，矩阵可以更节省空间，但我们正在处理足够小的数字，这无关紧要。
0赞
Dave
3/17/2021
请注意，这些数字会变大。k-moves 列的总和为 3^k。
0赞
btilly
3/17/2021
错误。您正在计算以 0 结束的方式。事实上，你可以< 0 结束。因此，（1， 1） 条目应为 3，因为 a 有 3 种获胜方式。
0赞
Dave
3/17/2021
@btilly 1,1 条目是在 1 步中失去 1 点生命值的方法数，即 0。我计算了获得高达 106 马力损失的方法。在一次移动中，您可能会失去 2、5 或 7 点生命值，因此这些行在 1 列中的计数为 1，在其他地方为 0。
0赞
Dave
3/17/2021
虽然 0,0 应该是 1，因为有一种方法可以在 0 步中输掉。
1赞
btilly
3/17/2021
#2
对于任何 dp 问题，通常最简单的方法是将解决方案编写为递归函数，然后进行缓存。
这是解决方案
def ways_for_a_to_win (a_hp, b_hp, moves=None, cache=None):
if moves is None:
moves = [2, 5, 7]
if cache is None:
cache = {}
if a_hp <= 0:
return 0
elif b_hp <= 0:
return 1
else:
if (a_hp, b_hp) not in cache:
answer = 0
for move in moves:
answer += ways_for_a_to_win(a_hp - move, b_hp, moves, cache)
answer += ways_for_a_to_win(a_hp, b_hp - move, moves, cache)
cache[(a_hp, b_hp)] = answer
return cache[(a_hp, b_hp)]
print(ways_for_a_to_win(100, 100))
评论
0赞
btilly
3/17/2021
@Dave我想我发现这很明显，因为这始终是我的第一个方法。写一个递归函数，记住。
上一个：如何确定两条二维线段是否重叠？
下一个：使用贝塞尔曲线闭合形状
评论
ways_a_wins[a_hp][b_hp]0 <= a_hp <= 1000 <= b_hp <= 100