时间戳

首页 > 解决方案 > 记住游戏算法的递归函数？

java - 记住游戏算法的递归函数？

问题描述

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

该功能的工作原理类似于移动点击游戏。用户可以执行 a) 点击 b) 升级。该函数找到达到指定数量的最少点击次数。用户可以跳过级别 - 因此绕过该级别的成本。

例如：

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

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

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

更有效的路线是：

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

现在我有一个适用于上述内容的递归程序。我尝试使用 2D 数组来记忆程序cache[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，这发生在两个递归函数交叉时，即具有相同的参数。

任何指导将不胜感激。

标签： javarecursionmemoization

解决方案

我看不出你只存储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在该循环中反复覆盖，因为您没有中断条件。所以你重新计算first每一个costs[i]小于current。你应该确保找到你 costs[i]想要的那个，并且first只计算那个。如果您只想找到第一个costs[i]小于 的current，只需添加一个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;
    }
}

如果要找到costs[i]小于的最小的current，则需要存储索引并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);
}

===

附带说明一下，您的代码有点混乱，可以使用一些很好的重构来提高可读性。例如，您可能想要创建一个用于保存原始参数的类并将其实例传递给fork. 适当的集合也可能比简单的数组更好。而且由于这些集合（数组）始终是相同的实例，因此您不需要将它们作为参数传递。让他们成为你班级的成员，并使 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 方法的某种形式的指导。

推荐阅读