递归问题-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 (ind >= clubLengths.length()) return -1;
    if (dp[ind][holeLength] != 0) return dp[ind][holeLength];

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

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

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

    int result = Math.min(rec1, rec2);
    result = Math.min(result, rec3);

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

与递归一起，我添加了dp以降低时间复杂度。结果，时间复杂度将为O（k * n），其中k为holeLength，n为clubsLengths中的元素数。