Не вижу причины, по которой вы сохраняете только значение 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.Обязательно найдите one 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);
// ...
}
}
Возьмите этот последний бит с крошкой соли, я просто напечатал его как некоторую форму руководства для ООП подхода к вашему коду.