Hello 👋
Pour ce dernier épisode de la saison, on se retrouvait pour le 740 - Delete and earn, un problème noté medium avec les tags Array
, Hash Table
et Dynamic Programming
.
L’énoncé
Soit un tableau d'entiers
nums,
maximisez le nombre de points que vous obtenez en effectuant l'opération suivante autant de fois que vous le souhaitez :
Choisissez n'importe quel
nums[i]
et supprimez-le pour gagnernums[i]
points. Ensuite, vous devez supprimer chaque élément égal ànums[i] - 1
et chaque élément égal ànums[i] + 1.
Renvoyez le nombre maximum de points que vous pouvez gagner en appliquant l'opération ci-dessus un certain nombre de fois.
Contraintes:
1 <= nums.length <= 2 * 10^4
1 <= nums[i] <= 10^4
L’intuition 💡
Le patron de résolution pour un problème de Dynamic Programming s’articule autour des 3 points suivants:
Quelles sont les conditions aux limites permettant d’arrêter la résolution?
Quelle est ma relation de récurrence?
On souhaite exprimer la réponse au problème de dimension n comme une combinaison de réponse à ce même problème dans des dimensions inférieures, jusqu’à retomber aux conditions aux limites.Quelle structure de donnée puis-je utiliser pour suivre l’état de ma résolution à mesure que je parcours l’espace des solutions?
Ici, la plus grande difficulté réside dans le choix de la structure de données 🤔
Si un array de dimension n, de dimension n x n ou bien une hash map font souvent l’affaire (n étant la taille de la liste en entrée), une structure adaptée est ici un array de dimension m, m étant la valeur maximale de tous les éléments possibles dans la liste d’entrée de taille n.
La solution est inspirée du post d’Alexander, que j’ai adapté en Python.
Dans chaque case de ce tableau de taille m, on met le nombre total de points que l’on récupère si on considère ce bucket.
ℹ️ En effet, si on choisit de prendre un nombre, autant prendre toutes ses instances dans la liste c.f., Hint 1.Voir les lignes 5 à 9: 👇
import collections | |
class Solution: | |
def deleteAndEarn(self, nums: List[int]) -> int: | |
m: int = max(nums) | |
buckets: List[int] = [0 for _ in range(m+1)] | |
counter = collections.Counter(nums) | |
for k, v in counter.items(): | |
buckets[k] = v*k | |
take, skip = 0, 0 | |
for i in range(m+1): | |
take_i = skip + buckets[i] | |
skip_i = max(skip, take) | |
skip = skip_i | |
take = take_i | |
return max(take, skip) |
Ensuite, pour la relation de récurrence, la magie de la DP opère des lignes 11 à 15, on définit deux variables, take_i
et skip_i
:
take_i
correspond à la solution du sous problème considérant les (i+1) premiers buckets (de 0 à i), en incluant les points du i-ème bucket.skip_i
correspond à la solution du sous problème considérant les (i+1) premiers buckets (de 0 à i), en excluant les points du i-ème bucket.
Pour tout i, la solution du problème est donnée par le maximum de (skip_i, take_i
).
Complexité
O(m) en espace pour stocker nos buckets.
O(m) en temps d’exécution.
Une passe pour la constitution ducounter
, une autre pour la mise à jour debuckets
puis une dernière pour calculer les valeurs detake
etskip.
Vidéo
Summer break 🏖
C’est l’été! On prend un break avec @Vincent pour se ressourcer et réfléchir à de nouveaux formats pour la rentrée. Prochaine session le samedi 4 septembre !
Take care, on se retrouve début septembre 😉
Your friends at LeetrGrind,
Photo de thumbnail par Sanndy Anghan