去年在一次采访中有人问我：
问。您可以通过多少种方式在 6 个球/交付中至少得分 6 个？
规则：有可能从一个球/交付中获得 0、1、2、3、4、5 或最多 6 分。每个球都是有效的(没有额外的球(。当总分达到或超过6分时，游戏结束(即使还有球也无需得分(。
例如： 可能的方法：[0
， 0， 2， 0， 0， 4]， [6]， [1， 1， 1， 3]， [2， 3， 0， 0， 0， 6] 等等。[0， 3， 4， 5] 不是一个正确的方式，因为第 3 个球的得分为 6。
我必须编写一个代码，该代码将找到可以完成的不同方式的数量。
我尝试过：
我试图使用"爬楼梯问题"来解决这个问题，一个人一次可以爬 1、2 或 3 个楼梯。有多少种方法可以到达第n个楼梯。
以下是楼梯问题的递归解决方案：
public static long possibleWaysRec(int n)
{
if (n == 0 || n == 1)
return 1L;
if (n == 2)
return 2L;
return (possibleWaysRec(n - 1) + possibleWaysRec(n - 2) + possibleWaysRec(n - 3));
}
现在，这两个问题之间的区别在于，在楼梯问题中，总楼梯是已知的(这里是目标分数(，并且对所需的步骤没有限制，但在我的问题中，我有 6 次机会。另一个区别是，分数可能不会在每次分时(当 0 分时(增加，但在楼梯位置必须随着每一步而改变(无论 1、2 或 3(。
我需要以某种方式修改它，以跟踪我用来达到目标分数的球数。 或任何其他解决此问题的方法，以便我可以在需要时找到所有可能的组合。
我递归地解决了这个问题，类似于你的"爬楼梯问题"，它有一个列表来跟踪到目前为止使用的球，因此它不超过可用/允许的球。
您也可以获得所有可能的方法(只需显示列表值。
public class WaysToScore
{
static long count=0;
public static void waysToDo(int score, int target, List<Short> waySoFar)
{
if(waySoFar.size() > 6) return; // total balls
if(score >= target && score < target+6)
{
count++;
return;
}
for(short i=0; i<=6; i++) // scoring options per ball
{
waySoFar.add(i);
waysToDo(score+i, target, waySoFar);
waySoFar.remove(waySoFar.size()-1);
}
}
public static void main(String[] args)
{
int target = 6 ; // total scores.
waysToDo(0, target, new ArrayList<Short>());
System.out.println("Total ways: "+count);
}
}
输出：Total ways: 2311
如果我正确理解了这个问题，也许我没有，那么我会用六个嵌套循环来做：
count_the_ways = 0;
for a from 0 to 6:
for b from 0 to 6:
[...]
if (a+b+c+d+e+f >= 6) count_the_ways++
这种方式的答案是116,275.
如果你想说"一旦总数等于或超过六，你就应该停止扔球"，这很容易用if语句来完成，例如
if (a+b) < 6:
for c from 0 to 6 ...
当它说"6或更多"时，描述不太清楚。也许我们想要：
for c from 0 to 6-(a+b) ...
等等。
递归变体当然是可能的，但在这种情况下相对没有必要。