Сложность: medium
Вам дан массив целых чисел nums. Изначально вы находитесь на первом индексе массива, и каждый элемент массива представляет вашу максимальную длину прыжка в этой позиции.
Верните true, если вы можете достичь последнего индекса, или false в противном случае.
Пример:
Input: nums = [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.
👨💻Алгоритм:
1️⃣ Инициализация таблицы памяти:
Изначально все элементы таблицы памяти имеют статус UNKNOWN, за исключением последнего, который является (тривиально) GOOD (может достичь сам себя).
2️⃣Модификация алгоритма обратного трассирования:
Измените алгоритм обратного трассирования таким образом, чтобы на рекурсивном шаге сначала проверялось, известен ли индекс (GOOD/BAD).
Если индекс известен, тогда возвращается True/False.
3️⃣Выполнение и сохранение результатов:
Если индекс не известен, выполняйте шаги обратного трассирования, как ранее.
После определения значения текущего индекса, сохраните его в таблице памяти.
😎 Решение:
let memo;
const canJumpFromPosition = (position, nums) => {
if (memo[position] != "UNKNOWN") {
return memo[position] == "GOOD";
}
let furthestJump = Math.min(position + nums[position], nums.length - 1);
for (
let nextPosition = position + 1;
nextPosition <= furthestJump;
nextPosition++
) {
if (canJumpFromPosition(nextPosition, nums)) {
memo[position] = "GOOD";
return true;
}
}
memo[position] = "BAD";
return false;
};
var canJump = function (nums) {
memo = new Array(nums.length).fill("UNKNOWN");
memo[memo.length - 1] = "GOOD";
return canJumpFromPosition(0, nums);
};
Ставь 👍 и забирай 📚 Базу знаний