Le problème 55 de Leetcode, appelé Jeu du Saut, consiste à vérifier si on peut atteindre le dernier index d'un tableau en partant du premier, où chaque élément indique la distance maximale de saut autorisée.

Plusieurs méthodes algorithmiques s'appliquent, incluant le backtracking, la programmation dynamique et l'approche greedy. Le backtracking explore tous les chemins récursifs, mais sa complexité le rend inadapté aux grands ensembles de données.

Approche par backtracking (non optimale)

Cette technique récursive tente d'explorer tous les sauts possibles. Elle est simple mais dépasse souvent le temps limite pour les grands tableaux.

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        found = False
        def backtrack(curr_pos):
            nonlocal found
            if curr_pos == len(nums) - 1:
                found = True
                return
            if curr_pos >= len(nums):
                return
            for step in range(1, nums[curr_pos] + 1):
                backtrack(curr_pos + step)
        backtrack(0)
        return found

Programmation dynamique récursive avec mémoïsation

En utilisant un cache pour stocker les résultats intermédiaires, cette version améliore l'efficacité en évitant les calculs redondants.

from functools import lru_cache

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        @lru_cache(maxsize=None)
        def dp(idx):
            if idx == len(nums) - 1:
                return True
            if idx >= len(nums):
                return False
            for jump in range(1, nums[idx] + 1):
                if dp(idx + jump):
                    return True
            return False
        return dp(0)

Programmation dynamique avec tableau itératif

On construit un tableau booléen de droite à gauche pour déterminer si chaque position est accessible.

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        reachable = [False] * len(nums)
        reachable[-1] = True
        for i in range(len(nums) - 2, -1, -1):
            max_step = nums[i]
            for step in range(1, max_step + 1):
                if i + step < len(nums) and reachable[i + step]:
                    reachable[i] = True
                    break
        return reachable[0]

Une approche greedy basée sur la portée maximale peut aussi résoudre le problème en temps linéaire, mais n'est pas détaillée ici.