Algorithm to get all combinations of (American) football point

It was one of my interview question, and I could not think of the good way to get number N. (plus, I did not understand the American football scoring system as well)

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

What would be an efficient algorithm to get all combinations of point-accumulations necessary to get a certain score N?

---

Assuming here you are looking for a way to get number of possibilities and not the actual possibilities.

First let's find a recursive function :

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 and f(n) = -infinity [n<0]

The idea behind it is: You can always get to 0 , by a no scoring game. If you can get to f(n-6) , you can also get to f(n) , and so on for each possibility.

Using the above formula one can easily create a recursive solution.

Note that you can even use dynamic programming with it, initialize a table with [-5,n], init f[0] = 0 and f[-1] = f[-2] = f[-3] = f[-4] = f[-5] = -infinity and iterate over indexes [1,n] to achieve the number of possibilities based on the the recursive formula above.

EDIT:
I just realized that a simplified version of the above formula could be:
f(n) = f(n-6) + f(n-1) + f(n-2) + f(n-3)
and base will be: f(0) = 1 , f(n) = 0 [n<0]
The two formulas will yield exactly the same result.

---

This is identical to the coin change problem, apart from the specific numbers used. See this question for a variety of answers.

---

You could use dynamic programming loop from 1 to n, here is some pseudo code:

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]

this way complexity is O(N), instead of exponential complexity if you compute recursively by subtracting from the final score... like computing a Fibonacci series.

I hope my explanation is understandable enough..

链接地址: http://www.djcxy.com/p/40212.html

上一篇: 在2048年游戏中合并拼贴的高效通用算法

下一篇: 算法获得（美式）足球点的所有组合