算法获得（美式）足球点的所有组合
这是我的面试问题之一，我想不出得到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将会是一种有效的算法？
假设在这里你正在寻找一种获得可能性的方法，而不是实际的可能性。
首先让我们找到一个递归函数 ：
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)
base： f(0) = 1和f(n) = -infinity [n<0]
其背后的想法是：通过一个没有得分的游戏，你总是可以达到0 。 如果你可以得到f(n-6) ，你也可以得到f(n) ，以此类推。
使用上述公式可以轻松创建递归解决方案。
请注意，您甚至可以使用动态编程 ，使用[-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)
并且base将是： f(0) = 1 ， f(n) = 0 [n<0]
这两个公式将产生完全相同的结果。
除了使用的具体数字之外，这与硬币更换问题相同。 看到这个问题的各种答案。
你可以使用从1到n的动态编程循环，下面是一些伪代码：
results[1] = 1
for i from 1 to n :
results[i+1] += results[i]
results[i+2] += results[i]
results[i+3] += results[i]
results[i+6] += results[i]
这种方式的复杂性是O（N），而不是指数复杂性，如果通过从最终得分中减去来递归计算的话......就像计算斐波那契数列一样。
我希望我的解释足够容易理解..
链接地址: http://www.djcxy.com/p/40211.html上一篇: Algorithm to get all combinations of (American) football point