Leetcode 55 Jump Game

You are given an integer array nums. You are initially positioned at the array’s first index, and each element in the array represents your maximum jump length at that position.

Return true if you can reach the last index, or false otherwise.

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.

Input: nums = [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.

• Bu soruda bize bir liste veriliyor.Listenin başından başlayarak her adımda bulunduğumuz indeksin değeri kadar zıplama şansımız var. Listenin sonuna ulaşabilirsek true ulaşamazsak false dönmemiz isteniyor.
• [2,3,1,1,4] 0. indeksteyiz 2 zıplama şansımız var .İster 1 zıplayarak 3 değerinin olduğu indekse istersek 2 zıplayarak 1 değerinin olduğu indekse atlayabiliriz.
• Bu proble hem dinamik programlama hem de greedy yöntemi ile çözülebilir.
• Greedy yönteminde sondan başlayarak önceki adımı bulmaya çalışırız.
• Hedefimiz 4. indeks peki kendi indeksi ve değerinin toplamı 4 olan bir değer var mı ? 3. indeks böyle bir değer hedefimiz artık 3. indeks oldu.
• Yeni hedefe ulaşmak için yine bir adım geri gidelim 2. indeks ve değerinin toplamı 3 oluyor.Bu durumda yeni hedef 2. indeks.
• Bu şekilde sondan başlayarak aramamızı yaparız. 0. indekse ulaşabilirsek o zaman baştan sona ilerleyebiliriz demektir True döneriz aksi taktirde False döneriz.

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        goal = len(nums) - 1

        for i in range(len(nums) -1, -1, -1):
            if i + nums[i] >=goal:
                goal = i
        return True if goal == 0 else False