这是如何工作的：CodeWars

Question

我在 CodeWars 上遇到了一项任务。由于没有解决这个问题，我决定看看那些已经通过的人的解决方案。 作为一个初学者，我什么都不懂。 Chat-GPT在要求解释时不一致。 帮助我了解这里发生了什么。

`def outcome(n, s, k):
    from math import comb
    if not k: return 1
    if not n or k < n: return 0
    return sum((-1) ** i * comb(n, i) * comb(k - s * i - 1, k - s * i - n) for i in range((k - n) // s + 1))

`

说明： 你有 n 个骰子，每个骰子都有 s 面，编号从 1 到 s。有多少个结果加起来达到指定的数字 k？

例如，如果我们掷四个普通的六面骰子，我们会得到四个结果，加起来为 5。

(1, 1, 1, 2) (1, 1, 2, 1) (1, 2, 1, 1) (2, 1, 1, 1) 

有 100 项随机测试：

0 <= n <= 10
1 <= s <= 20
0 <= k <= n * s

备注：

无论你有多少骰子，总有 1 种情况达到 k = 0 没有任何骰子，不可能达到任何正 k

最初，我想到使用递归但均匀地解决这个练习。 然后我在论坛中寻找类似物，但再次失败。

Answer 1

为了您的兴趣，可以递归地执行此操作。其实很简单：

def outcome(n, s, k):
    dp = [[0] * (k+1) for _ in range(n+1)]
    dp[0][0] = 1  

    for i in range(1, n+1):
        for j in range(1, k+1):
            for x in range(1, min(s, j)+1):
                dp[i][j] += dp[i-1][j-x]

    return dp[n][k]

举个例子：

n = 4
s = 6
k = 5
print(outcome(n, s, k))

返回4。

我认为递归方法可以更好地解释正在发生的事情：首先创建一个二维数组

dp

（维度为

(n+1) x (k+1)

），以使用

i

骰子存储每个可能总和的结果数量。这个空间用于当骰子数量或目标总和为 0 时，考虑基本情况。为基本情况设置

dp[0][0] = 1

，即只有 1 种方法可以用 0 个骰子获得 0 的总和。然后，循环遍历该数字。骰子并循环遍历从 1 到 k 的所有目标。对于每个目标总和

j

，考虑滚动当前骰子的所有可能结果，由变量

x

表示，从 1 到

x

进行迭代。

min(s, j)

确保您考虑的结果不会高于边数

min(s, j)

或当前目标总和

s

。 最后，对于每个结果

j

，将结果数与之前的数相加。将骰子

x

和剩余目标总和

(i-1)

放入当前单元格

(j-x)

。