记忆游戏算法的递归函数？

Question

我有一个作业的递归函数。但是，部分要求是通过使用记忆来降低复杂性。

该功能类似于手机点击游戏。用户可以执行 a) a) a) b) upgrade。该函数找到达到指定数量的最少点击次数。用户可以跳过级别 - 从而绕过该级别的成本。

例如：

Levels: 0, 1, 2.
Cost of upgrades: 0, 5, 8.
Money per tap: 2, 4, 9.

其中一条路线，所需金额为 15 美元：

点击三次可获得 $2 x 3 美元。 (还剩 6 美元。)
升级只需 5 美元（还剩 1 美元。）
点击两次可获得 $4 * 2 + $1 美元。（还剩 9 美元。）
升级只需 8 美元（还剩 1 美元。）
点击两次以达到所需金额（$19 > $15。）

总共 3 + 2 + 2 = 7 个水龙头。

更有效的路线是：

点击四次可获得 $2 x 4 美元。 (还剩 8 美元。)
升级 8 美元，跳过二级升级。 ($0 剩余。)
点击两次以达到所需金额（$18 > $15。）

总共 4 + 2 = 6 个水龙头。

现在我有一个适用于上述内容的递归程序。我尝试使用二维数组 cache[levels][amount] 记忆程序，其中存储每个 levels/amount 的抽头并在需要时访问。

一个最小的工作解决方案如下：

import java.io.*;
import java.math.*;
import java.util.*;

class IdleGame {

  private static int fork(int current, int required, int level, int taps, int[] values, int[] costs, int maxLevel,
      int[][] cache) {
    int first = Integer.MAX_VALUE;
    int second = Integer.MAX_VALUE;

    if (current >= required) {
      return taps;
    }
    //upgrade path, call recursively if available.
        for (int i = level + 1; i <= maxLevel; i++) {
  if (current >= costs[i]) {
    if (cache[i][current] == 0) {
      first = fork(current - costs[i], required, i, taps, values, costs, maxLevel, cache);
      cache[i][current] = first;
    } else {
      // System.out.println("First");
      first = cache[i][current];
    }
  }
}

if (cache[level][current] == 0) {
  second = fork(current + values[level], required, level, taps + 1, values, costs, maxLevel, cache);
  cache[level][current] = second;
} else {
  // System.out.println("Second");
  second = cache[level][current]--;
}

    return first < second ? first : second;
  };

  public static void main(String[] args) {
      int[] values = {2,4,9};
      int[] costs = {0,5,8};
      int[][] cache = new int[3][16];
      int solution = fork(0, 15, 0, 0, values, costs, 2, cache);
          System.out.println(solution);
    }
}

但是，这个解决方案对于我的测试用例来说不够快。据我所知，当有另一个调用相同的递归函数实例时，我正在使用记忆值 level/value，当两个递归函数交叉时会发生这种情况，即具有相同的参数。

任何指导将不胜感激。

Answer 1

我看不出为什么只存储 second 值而不存储 first 的原因。实际上你应该简单地存储最终结果并在方法开始时检查它：

private static int fork(int current, int required, int level, int taps, int[] values, int[] costs, int maxLevel, int[][] cache) {

    if (current >= required)
        return taps;

    // check cache, calculate value only if cache is empty
    if (cache[level][current] == 0) {

        // calculate first value
        int first = Integer.MAX_VALUE;
        for (int i = level + 1; i <= maxLevel; i++) {
            if (current >= costs[i]) {
                first = fork(current - costs[i], required, i, taps, values, costs, maxLevel, cache);
            }
        }

        // calculate second value
        int second = fork(current + values[level], required, level, taps + 1, values, costs, maxLevel, cache);

        // store result in cache
        cache[level][current] = first < second ? first : second;
    }

    // return cached value
    return cache[level][current];
}

顺便说一句，通过检查值是否为 0 来检查缓存是否已设置，通常不是一个好主意。如果有效结果实际上可以为 0 怎么办？最好使用可空类型或可以检查密钥是否存在的容器。

我注意到的另一件事是，根据您的输入，您在该循环中重复覆盖 first，因为您没有中断条件。因此，您为每个小于 current 的 costs[i] 重新计算 first。您应该确保找到您想要的 one costs[i]，并仅为此计算 first。如果您只想找到第一个小于 current 的 costs[i]，只需添加一个 break:

for (int i = level + 1; i <= maxLevel; i++) {
    if (current >= costs[i]) {
        first = fork(current - costs[i], required, i, taps, values, costs, maxLevel, cache);
        break;
    }
}

如果要找到小于current的最小costs[i]，需要存储索引，在循环后调用fork：

// find smallest costs[i] smaller than current:
int smallestCostIndex = -1;
int smallestCost = Integer.MAX_VALUE;
for (int i = level + 1; i <= maxLevel; i++) {
    if (current >= costs[i] && costs[i] < smallestCost) {
        smallestCost = costs[i];
        smallestCostIndex = i;
    }
}
// calculate first using smallest costs[i] smaller than current (if it exists):
int first = Integer.MAX_VALUE;
if (smallestCostIndex >= 0) {
    first = fork(current - costs[i], required, i, taps, values, costs, maxLevel, cache);
}

===

附带说明一下，您的代码有点混乱，可以使用一些好的重构来提高可读性。例如，您可能想要创建一个 class 来保存原始参数并将其实例传递给 fork。适当的集合也可能比简单的数组更好。由于这些集合（数组）始终是相同的实例，因此您不需要将它们作为参数传递。让他们成为你的 class 的成员，并使 fork 成为一个非静态方法。像这样：

class GameParams {
    private int current;
    private int required;
    private int level;
    private int taps;

    // constructor, getters etc.
}

class GameState {
    private int value;
    private int cost;

    // constructor, getters etc.
}

class Game {

    private int maxLevel;                   // initialized to 2 in your case
    private List<GameState> states;         // initialized to {GameState(2,0), GameState(4,5), GameState(9,8)} in your case
    private Map<GameParams, int> cache;

    // constructor, getters etc.

    private int fork(GameParams params) {   // called with GameParams(0, 15, 0, 0)
        if (chache.contains(params))
            return cache.get(params);

        // ...
    }

}

对最后一点持保留态度，我只是将其作为某种形式的 OOP 方法指南输入到您的代码中。

记忆游戏算法的递归函数？

Memoizing a recursive function for a game algorithm?

java

recursion

memoization