InterviewStreet的保龄球计数算法(Bowling Counting algorithm from InterviewStreet)

 我不知道这是不是正确的部分...但是这里有： 
 
 上周的面试比赛（Code Sprint 3）有一个叫做保龄球的问题。 （10针保龄球，N帧）。 重点是计算通过播放N帧来获得M分的方式的数量。 
 
 问题陈述在这里： http ： //pastebin.com/cyeLML8U 
 
 我很确定我已经使用2维DP解决了这个问题。 但是，我得到第3个样本数据错误（1帧，25分）。 样本答案是1，但我得到6。 
 
 这是他们对样本答案的解释： 
 
For the third case, there is only 1 way. Score a strike in the first frame, score another strike with the first extra ball, and an additional 5 with the second extra ball.
 
 但是，你不能在第一帧（也是唯一一帧）中获得一次击球，然后在随后的额外帧中得分以下任何一项？ 
 
10 5
9 6
8 7
7 8
6 9
5 10
 
 我无法理解为什么“1”是正确的答案....我也看过维基百科的规则。 
 
 他们的回答可能是正确的，我可能忽略了一些非常明显的事情。 谁能告诉我答案有什么问题？ 

I don't know if this is the right section... but here goes:
 
Last weeks contest on interviewstreet (Code Sprint 3) had a problem called bowling. (10 pin bowling, N frames). The point is to count the number of ways to score M points by playing N frames.
 
Problem Statement is here: http://pastebin.com/cyeLML8U
 
I'm pretty sure I've solved the problem using 2 dimensional DP. However, I get the 3rd sample data wrong (1 Frame, 25 points). The sample answer is 1, however I get 6. 
 
This is their explanation of the sample answer:
 
For the third case, there is only 1 way. Score a strike in the first frame, score another strike with the first extra ball, and an additional 5 with the second extra ball.
 
However, can't you score a strike in the first (and only) frame, then score any of the following in the subsequent extra frames?
 
10 5
9 6
8 7
7 8
6 9
5 10
 
I can't wrap my head around why "1" is the right answer.... I've looked on wikipedia for the rules too.
 
Their answer is probably right, and I'm probably overlooking something REALLY obvious. Can anyone tell me what's wrong with my answer?

原文：https://stackoverflow.com/questions/13147654