Возвращайте правильное значение на каждой итерации – динамическое программирование
Проблема выглядит следующим образом:
Компьютерщик собирается на дневную программу тренировок. Он может выполнять любое из этих трех действий: бег, борьба и учебная практика. Каждое занятие имеет определенный смысл в каждый день. Поскольку Гик хочет улучшить все свои навыки, он не может заниматься одним и тем же делом два дня подряд. Помогите Гику максимизировать свои очки заслуг, поскольку вам предоставляется двумерный массив очков, соответствующий каждому дню и виду деятельности.
Вот как я пытаюсь подойти. Я беру каждое значение массива и рекурсивно вызываю следующий индекс, передавая предыдущий индекс, чтобы пропустить его значение при расчете.
Я ошибаюсь, потому что возвращаю this.currentMax, который продолжает добавляться к points[index][j], тогда как я бы предпочел, чтобы на каждом шаге вычисления происходили только для этой итерации, и если она больше this.currentMax, последняя должна обновляться. Как я могу это исправить? Цените любую помощь.
class Solution {
//Function to find the maximum points among all the possible ones.
currentMax = -Infinity;
maximumPoints(points, n, index=0, prev=-1)
{
if (index === n) return 0;
for(var j=0; j<points[index].length; j++){
//skip the prev index
if (j !== prev){
var temp = points[index][j] + this.maximumPoints(points, n, index+1, j);
this.currentMax = Math.max(this.currentMax, temp);
}
}
return this.currentMax //This is where perhaps going wrong
}
}
var x = new Solution();
console.info(x.maximumPoints([[1,2,5], [6, 2, 10]], 2))Обновлено: Предложения @Bergi работают. Но вот что меня еще смущает. Когда мы создаем локальную переменную maxPoint, разве следующий рекурсивный вызов не должен снова и снова сбрасывать эту переменную в 0.
Например, f(([[1,2,5], [6, 2, 10]], 2, index=0, prev=-1) будет генерировать
1+ f(([[1,2,5], [6, 2, 10]], 2, index=1, prev=0)
2 + f(([[1,2,5], [6, 2, 10]], 2, index=1, prev=0)
5 + f(([[1,2,5], [6, 2, 10]], 2, index=1, prev=0)
Но в каждом из этих вызовов maxPoint будет обновляться с помощью Max того, что возвращается, и 0 (ноль, поскольку каждый раз сбрасывается?)
Ценю разъяснения:
class Solution {
//Function to find the maximum points among all the possible ones.
maximumPoints(points, n, index=0, prev=-1)
{
if (index === n) return 0;
let maxPoint = 0;
for(var j=0; j<points[index].length; j++){
//skip the prev index
if (j !== prev){
var temp = points[index][j] + this.maximumPoints(points, n, index+1, j);
maxPoint = Math.max(maxPoint, temp);
}
}
return maxPoint;
}
}
var x = new Solution();
console.info(x.maximumPoints([[1,2,5], [6, 2, 10]], 2))Не делайте currentMax свойство экземпляра, просто создайте локальную переменную в функции?
Вероятно, вам нужна не одна переменная currentMax, а одна для каждого действия, выполненного в день. Кроме того, для динамического программирования вам действительно нужно создать таблицу промежуточных результатов и использовать ее в качестве кеша, я не вижу этого нигде в вашем коде.
@Берги Спасибо. Создание локальной переменной сработало. Но это почему-то не кажется интуитивным, поскольку я считаю, что нам нужно сохранить один глобальный максимум. Можете ли вы объяснить? Да, я планировал запомнить, как только это начнет работать.
maxPoint сохраняет максимальную точку рекурсивных вызовов в цикле. Это не глобальный максимум, а локальный максимум для одного вызова. Глобальный максимум является локальным максимумом корневого вызова, поскольку этот локальный максимум корневого вызова был вычислен на основе максимумов его дочерних элементов, вплоть до нижнего уровня.
![Безумие обратных вызовов в javascript [JS]](https://i.imgur.com/WsjO6zJb.png)
Ответы 1
Как вы указываете, непосредственная проблема заключается в том, что this.currentMax продолжает добавляться и никогда не возвращается к предыдущему значению при выходе из рекурсии, и поэтому он представляет собой сумму значений из нескольких ветвей вашего дерева рекурсии.
Первое решение, на которое следует обратить внимание, — это передать currentMax в качестве аргумента: таким образом, она станет локальной переменной, которая не повлияет на переменную вызывающего объекта с тем же именем. См. также ответ на ваш дополнительный вопрос ниже.
Но тут мы подходим к другим проблемам:
Этот алгоритм ищет все возможные пути, которые можно сделать. Поскольку при вызове кода вам может быть передан массив, содержащий до ста тысяч записей, вы попытаетесь посетить 2100000 состояния, что практически невозможно, даже если ваш компьютер (или самый быстрый суперкомпьютер) будет работать до конца вашей жизни.
Вы можете предотвратить этот экспоненциальный взрыв, используя мемоизацию.
Но тогда вы столкнетесь с пределом стека вызовов. Ограничение на стек вызовов JS может не поддерживать глубину 100000. Тогда следует преобразовать алгоритм в итеративный:
Итерационный алгоритм
Вы можете применить эту логику:
Отслеживайте лучший результат, когда мы заканчиваем на index и выбираем в качестве последнего действия 0, 1 или 2: таким образом, у нас есть три «лучших».
Когда index увеличивается, эти лучшие результаты можно обновить следующим образом:
- Выбираем активность 0: берём
points[0]и прибавляем максимум предыдущих лучших результатов, которые у нас были для активности 1 и 2. - Аналогичным образом мы можем определить лучшие результаты для других видов деятельности по индексу
index, и таким образом мы получим три обновленных лучших результата, по одному для каждого вида деятельности.
Вот реализация спойлера, основанная на этом подходе:
maximumPoints(points, n) { let dp = points[0]; for (let index = 1; index < n; index++) { const [a, b, c] = points[index]; dp = [ a + Math.max(dp[1], dp[2]), b + Math.max(dp[0], dp[2]), c + Math.max(dp[0], dp[1]), ]; } return Math.max(...dp); }
Дополнительный вопрос
Когда мы создаем локальную переменную
maxPoint, разве следующий рекурсивный вызов не должен снова и снова сбрасывать эту переменную в 0?
Каждый из них сбрасывает свою переменную; Эта инициализация не влияет на переменную вызывающего абонента с тем же именем.
Переменная maxpoint действительно локальная и на нее не влияют рекурсивные вызовы. В вашем коде maxpoint получает значение, возвращаемое рекурсивным вызовом, и с этого момента будет по крайней мере это значение. В следующей итерации оно может стать еще лучше. Когда return maxPoint выполняется, он будет представлять лучшее значение, которое можно объединить из рекурсивного вызова и значения текущей точки.
И вот мы получаем такой эффект: при раскручивании рекурсии составляются суммы, в которых представлен каждый point с большим индексом. В конечном итоге вызывающая сторона верхнего уровня получит сумму, состоящую из значений 𝑛, каждое из которых происходит из отдельной записи points.
Спасибо. Но не могли бы вы объяснить разъяснение, которое я искал в разделе «РЕДАКТИРОВАТЬ», то есть, как локальная переменная не будет сбрасываться каждый раз и работать нормально, возможно, с тем же примером?
Сумма формируется изнутри наружу. Да, все вызовы начинаются со своего maxPoint 0, но в конце return он будет иметь значение, соответствующее некоторому points[index][j] плюс всему, что вернулось из рекурсии. Таким образом, пока рекурсия завершается, возвращаемое значение становится все больше и больше, и верхний вызывающий объект получит сумму, состоящую из n членов.
Это очень ясно. Спасибо.
использовать функцию генератора