3

我不知道这是否是正确的部分......但这里是：

上周在 interviewstreet (Code Sprint 3) 上的比赛有一个叫做保龄球的问题。（10 针保龄球，N 帧）。重点是统计播放N帧获得M分的方法数。

问题陈述在这里： http: //pastebin.com/cyeLML8U

我很确定我已经使用二维 DP 解决了这个问题。但是，我得到了第三个样本数据错误（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”是正确答案....我也在维基百科上查看了规则。

他们的回答可能是正确的，我可能忽略了一些非常明显的东西。谁能告诉我我的答案有什么问题？

4

3 回答 3

3

你不能用第一个额外的球得到 9 个瓶，然后用第二个额外的球得到 6 个瓶，因为当你用第二个额外的球投球时，只剩下 1 个瓶了。

于 2012-10-30T21:16:14.710 回答
2

但如果第二球没有命中，就只有“捡到备用”的机会。也就是说，您只能获得 10 个引脚。因此，如果您在第一个球上被击中，然后在第二个球上被击中 9 个球，那么您在第三个球上最多可以得到 1 个。

于 2012-10-30T21:16:27.467 回答
1

我读它的方式，你的回答在技术上是正确的，但我认为这个问题没有被正确地提出。

在您问题链接中规定的限制范围内，我看不出您的解决方案有什么问题。在现实生活中，除非您将球瓶全部击倒或两次（或两次）击倒球瓶，否则球瓶实际上不会被重置，因此 - 正如其他人所说 - 您可以从 1 球框架中获得 25 分的唯一方法是真实的生命就是罢工，罢工，5。

基本上，这个问题没有给你正确的约束。我认为说你的答案错误是没有道理的，因为这个问题的措辞很糟糕。

于 2012-10-30T21:32:29.473 回答