获得特定分数所需的(美式)足球积分累积的所有组合的算法 N

Question

这是我的面试问题之一，我想不出获得 N 号的好方法。(另外，我也不了解美式足球计分系统)

6 points for the touchdown
1 point for the extra point (kicked)
2 points for a safety or a conversion (extra try after a touchdown)
3 points for a field goal

获得特定分数 N 所需的所有点累积组合的有效算法是什么？

Answer 1

假设您正在寻找一种方法来获取可能性的数量而不是实际的可能性。

首先让我们找到一个递归函数:

f(n) = (f(n-6) >= 0? f(n-6) : 0) + (f(n-1) >= 0 ? f(n-1) : 0) + (f(n-2) >= 0 ? f(n-2) : 0) + (f(n-3) >= 0 ? f(n-3) : 0)

基地:f(0) = 1和 f(n) = -infinity [n<0]

其背后的想法是:你总能到达0 , 通过一场没有得分的比赛。如果你能打到f(n-6) , 你也可以到 f(n) , 依此类推。

使用上面的公式可以很容易地创建一个 recursive解决方案。

请注意，您甚至可以使用 dynamic programming 用它，用[-5,n]初始化一个表，init f[0] = 0和 f[-1] = f[-2] = f[-3] = f[-4] = f[-5] = -infinity并遍历索引 [1,n]根据上面的递归公式来实现可能性的数量。

编辑:
我刚刚意识到上述公式的简化版本可能是:
f(n) = f(n-6) + f(n-1) + f(n-2) + f(n-3)
基地将是:f(0) = 1 , f(n) = 0 [n<0]
这两个公式将产生完全相同的结果。