Сложность: 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⃣Выполнение и сохранение результатов:
Если индекс не известен, выполняйте шаги обратного трассирования, как ранее.
После определения значения текущего индекса, сохраните его в таблице памяти.
😎 Решение:
enum Index {
case good, bad, unknown
}
class Solution {
var memo: [Index]
init(_ nums: [Int]) {
self.memo = Array(repeating: .unknown, count: nums.count)
self.memo[nums.count - 1] = .good
}
func canJumpFromPosition(_ position: Int, _ nums: [Int]) -> Bool {
if memo[position] != .unknown {
return memo[position] == .good
}
let furthestJump = min(position + nums[position], nums.count - 1)
for nextPosition in (position + 1)...furthestJump {
if canJumpFromPosition(nextPosition, nums) {
memo[position] = .good
return true
}
}
memo[position] = .bad
return false
}
func canJump(_ nums: [Int]) -> Bool {
return canJumpFromPosition(0, nums)
}
}Ставь 👍 и забирай 📚 Базу знаний