java - 递归问题 - Java - 高尔夫击球的最小次数

Question

我正在尝试根据给定的球杆长度计算需要的最少击球次数。您也可以将其视为给定找零所需的最小硬币数量。

我的代码是

   public static int golf(int holeLength, int[] clubLengths)
   {
   return golf(holeLength, clubLengths, 0);
   }

   public static int golf(int holeLength, int[] clubLengths, int shots)
   {
      if(holeLength==0) 
         shots+=0;
      else if(holeLength<0)
         shots=-1;
      else
      {      
         for(int i = 0; i<clubLengths.length; i++)
         {
            return golf(holeLength-clubLengths[i], clubLengths, shots+1);
         }
      }

      return shots;
   }

这里的问题是它似乎只根据数组中的第一个数字给出答案。例如，如果我有 {25,50,100} 并且我想得到 100。显然，只需要最少一次，但程序只会使用 25 来计算它并说 4。同样，如果第一个数字是 21，那么它只会给出 stackoverflow。

Answer 1

以下是代码中发生的情况:当函数运行第一个循环时，它获取 clubLengths 中的第一个元素并立即返回，而不进入下一个循环。您需要仔细检查每个可能使用的俱乐部。

这是我的递归解决方案:

1. 浏览每个俱乐部。
2. 您可以选择使用当前俱乐部并再次使用它，
3. 或者您可以选择使用当前俱乐部并使用下一个俱乐部，
4. 或者您可以选择不使用当前俱乐部并使用下一个俱乐部。

我可以通过以下方式实现:

public static int golf(int holeLength, int[] clubLengths) {
    int[][] dp = int[clubLengths.length()][holeLength+1];
    return golf(holeLength, clubLengths, 0, dp);
}

private static int golf(int holeLength, int[] clubLengths, int ind, int[][] dp) {
    if (holeLength == 0) return 0;
    if (holeLength < 0) return -1;
    if (ind >= clubLengths.length()) return -1;
    if (dp[ind][holeLength] != 0) return dp[ind][holeLength];

    int rec1 = golf(holeLength-clubLengths[ind], clubLengths, ind, dp);
    if (rec1 == -1) rec1 = Integer.MAX_VALUE;
    else rec1++;

    int rec2 = golf(holeLength-clubLengths[ind], clubLengths, ind+1, dp);
    if (rec2 == -1) rec2 == Integer.MAX_VALUE;
    else rec2++;

    int rec3 = golf(holeLength, clubLengths, ind+1, dp);
    if (rec3 == -1) rec3 = Integer.MAX_VALUE;

    int result = Math.min(rec1, rec2);
    result = Math.min(result, rec3);
    if (result == Integer.MAX_VALUE) result = -1;

    dp[ind][holeLength] = result;
    return result;
}

除了递归之外，我还添加了dp来优化时间复杂度。因此，我的解决方案的时间复杂度为 O(k*n)，其中 k 是 holeLength，n 是 clubsLengths 中的元素数量。如果您不需要dp并且只想纯粹的递归，您可以从上面删除所有dp的用法，代码仍然可以工作，但速度较慢。