Два игрока по очереди выбирают одну из внешних монет. В конце мы рассчитываем разницу между оценкой, которые получают два игрока, учитывая, что они играют оптимально. Например, список {4,3,2,1},
Оптимальная последовательность будет 4, 3, 2, 1. Затем я получу 4+2 = 6 баллов и оценки противника. /> < /p>
Моя задача - распечатать оценки, а также оптимальную последовательность в индексе. Таким образом, в массиве {4,3,2,1} оптимальная последовательность будет 0,1,2,3. < /p>
Максимальное время выполнения и память не должно превышать n^2. Поэтому я реализовал вышеупомянутый алгоритм с подходом к нижней части, что означает I*j, в соответствии с моему Algorithm, который является одним из Algoritmm, что является одним из Algoritm, что является одним из Algoritmm, что является одним из Algoritmm, что является одним из Algoritmm, что является одним из Algorithm, который является одним из Algoritm. Находит в правом верхнем углу (где i = 0 и j = n-1). Он работает, вычисляет оценки, но я понятия не имею, как проследить оптимальную последовательность во время выполнения, поскольку, когда я вычисляю подпроекты по подзадачам, только оценка будет сохранена и используется в следующей задаче, в то время как последовательность, которая привела к конечному результату, трудно отслеживать. Memo [j] ...... Ну, они работали, но необходимая память будет тогда больше, чем n^2, и это не разрешено в моей задаче. < /p>
Так что больше есть лучшая идея, которая не требует такого большого пространства памяти? />
public int maxGain(int[] values) {
int n = values.length;
int [][] memo = new int[n][n];
for (int i = 0; i < n; i++)
memo = values;
for (int i = 0, j = 1; j < n; i++, j++)
memo[j] = Math.max(values, values[j]);
for (int k = 2; k < n; k++) {
for (int i = 0, j = k; j < n; i++, j++) {
int a = values + Math.min(memo[i + 2][j], memo[i + 1][j - 1]);
int b = values[j] + Math.min(memo[i + 1][j - 1], memo[j - 2]);
memo[j] = Math.max(a, b);
}
}
return memo[0][n - 1];
}
Подробнее здесь: https://stackoverflow.com/questions/622 ... rogramming
