获得获得某个分数N所必需的（美国）足球点积累的所有组合的算法

6 回答

• 1

  假设您正在寻找一种方法来获得多种可能性，而不是实际的可能性 .

  首先让我们找一个 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)

  基地： f(0) = 1 和 f(n) = -infinity [n<0]

  它背后的想法是：你可以通过一个没有得分的游戏来获得 0 . 如果你可以到 f(n-6) ，你也可以到 f(n) ，等等 .

  使用上面的公式可以轻松创建一个recursive解决方案 .

  请注意，您甚至可以使用 dynamic programming ，使用[-5，n]，init f[0] = 0 和 f[-1] = f[-2] = f[-3] = f[-4] = f[-5] = -infinity 初始化表，并迭代索引 [1,n] 以根据上面的递归公式实现可能性的数量 .

  EDIT:
  我刚才意识到上述公式的简化版本可能是：
  f(n) = f(n-6) + f(n-1) + f(n-2) + f(n-3)
  和基数将是： f(0) = 1 ， f(n) = 0 [n<0]
  这两个公式将产生完全相同的结果 .

  回复于 2024-04-25T05:40:20+08:00
• 0

  除了使用的具体数字之外，这与硬币更换问题相同 . 有关各种答案，请参阅this question .

  回复于 2024-04-25T05:40:20+08:00
• 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），而不是指数复杂性，如果你通过从最终得分中减去来递归计算...就像计算Fibonacci系列一样 .

  我希望我的解释是可以理解的 .

  回复于 2024-04-25T05:40:20+08:00
• 3

  我知道这个问题已经过时了，但我看到的所有解决方案都有助于计算得分排列的数量而不是得分组合的数量 . （所以我认为这样的事情应该是答案，或者问题 Headers 应该改变 . ）

  一些代码如下（可以转换为dp）将计算不同分数的可能组合的数量：

  int getScoreCombinationCount(int score, int scoreVals[], int scoreValIndex) {
      if (scoreValIndex < 0)
          return 0;
      if (score == 0)
          return 1;
      if (score < 0)
          return 0;
  
  return getScoreCombinationCount(score - scoreVals[scoreValIndex], scoreVals, scoreValIndex) +
         getScoreCombinationCount(score, scoreVals, scoreValIndex - 1);
  }
  

  回复于 2024-04-25T05:40:20+08:00
• 0

  基于书 Elements of Programming Interviews 中的解决方案实现的此解决方案对于计算一组得分点的'combinations'（无重复集）的数量似乎是正确的 .

  例如，如果 points = {7, 3, 2} ，总分为 7 的 2 组合：

  {7} 和 {3, 2, 2} .

  public static int ScoreCombinationCount(int total, int[] points)
  {
      int[] combinations = new int[total + 1];
      combinations[0] = 1;
      for (var i = 0; i < points.Length; i++)
      {
          int point = points[i];
          for (var j = point; j <= total; j++)
          {
              combinations[j] += combinations[j - point];
          }
      }
  
      return combinations[total];
  }
  

  我不确定我是否理解逻辑 . 谁能解释一下？

  回复于 2024-04-25T05:40:20+08:00
• 0

  此问题的答案取决于您是否允许组合的总数包括重复的无序组合 .

  例如，在美式橄榄球比赛中，你可以得到2分，3分或7分（是的，我知道你可以在达阵时错过额外的分数，但是让我们忽略1分） .

  然后，如果你的目标 N 是5，那么你可以使用 {2, 3} 或 {3, 2} 来达到它 . 如果你把它算作两个组合，那么@amit的Dynamic Programming solution就可以了 . 但是，如果将这两个组合计为一个组合，则@Maximus的iterative solution将起作用 .

  下面是一些Java代码，其中 findWays() 对应于计算所有可能的组合，包括重复项，而 findUniqueWays() 对应于仅计算唯一组合 .

  // Counts the number of non-unique ways to reach N.
  // Note that this algorithm counts {1,2} separately from {2,1}
  // Applies a recurrence relationship. For example, with values={1,2}:
  // cache[i] = cache[i-1] + cache[i-2]
  public static long findWays(int N, int[] values) {
  
      long cache[] = new long[N+1];
      cache[0] = 1;
  
      for (int i = 1; i <= N; i++) {
          cache[i] = 0;
          for (int value : values) {
              if (value <= i)
                  cache[i] += cache[i-value];
          }
      }
  
      return cache[N];
  }
  
  // Counts the number of unique ways to reach N.
  // Note that this counts truly unique combinations: {1,2} is the same as {2,1}
  public static long findUniqueWays(int N, int[] values) {
  
      long [] cache = new long[N+1];
      cache[0] = 1;
  
      for (int i = 0; i < values.length; i++) {
  
          int value = values[i];
  
          for (int j = value; j <= N; j++) {
              cache[j] += cache[j-value];
          }
      }
  
      return cache[N];
  }
  

  以下是可能的点为 {2,3,7} 的测试用例 .

  private static void testFindUniqueWaysFootball() {
  
      int[] points = new int[]{2, 3, 7}; // Ways of scoring points.
      int[] NValues = new int[]{5, 7, 10}; // Total score.
      long result = -1;
  
      for (int N : NValues) {
          System.out.printf("\nN = %d points\n", N);
  
          result = findWays(N, points);
          System.out.printf("findWays() result = %d\n", result);
  
          result = findUniqueWays(N, points);
          System.out.printf("findUniqueWays() result = %d\n", result);
      }
  }
  

  输出是：

  N = 5 points
  findWays() result = 2
  findUniqueWays() result = 1
  
  N = 7 points
  findWays() result = 4
  findUniqueWays() result = 2
  
  N = 10 points
  findWays() result = 9
  findUniqueWays() result = 3
  

  上面的结果显示，要达到 N=7 点，那么有4种非独特方式（这些方式是 {7}, {2,2,3}, {2,3,2}, {3,2,2} ） . 但是，只有两种独特的方式（这些方式是 {7} 和 {2,2,3} ） . 但是， .

  回复于 2024-04-25T05:40:20+08:00