找到特定结果的 n 间隔动作的组合

Question

给定以下语句：

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

对于极端情况，玩家 A 和 B 都只用 2HP 攻击命中，我选择了 100 次重复。

当然，这会花费大量时间来计算。

我需要找到一个更快的算法。

Answer 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 wins) * (count of k-move loss) * choose(j+k-1, k) 到我们的总数。

例如最大 hp 为 10 的矩阵和 wins/losses 小计：

> 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

Answer 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))

找到特定结果的 n 间隔动作的组合

Finding the combinations of n-spaced actions to a specific result

python

language-agnostic

algorithm

combinations