Jeu de pierre II

1140. Jeu de pierre II

Difficulté :Moyen

Sujets :Tableau, mathématiques, programmation dynamique, somme de préfixes, théorie des jeux

Alice et Bob continuent leurs jeux avec des tas de pierres. Il y a un certain nombre de tas disposés en rangée, et chaque tas a un nombre entier positif de tas de pierres[i]. L'objectif du jeu est de terminer avec le plus de pierres.

Alice et Bob se relaient, Alice commençant en premier. Initialement, M = 1.

Au tour de chaque joueur, ce joueur peut prendre toutes les pierres des premières X piles restantes, où 1 <= X <= 2M. Ensuite, nous définissons M = max(M, X).

Le jeu continue jusqu'à ce que toutes les pierres aient été prises.

En supposant qu'Alice et Bob jouent de manière optimale, renvoyez le nombre maximum de pierres qu'Alice peut obtenir.

Exemple 1 :

• Entrée : piles = [2,7,9,4,4]
• Sortie : 10
• Explication : Si Alice prend une pile au début, Bob en prend deux, puis Alice en prend à nouveau 2. Alice peut obtenir 2 + 4 + 4 = 10 piles au total. Si Alice prend deux piles au début, alors Bob peut prendre les trois piles restantes. Dans ce cas, Alice obtient 2 + 7 = 9 piles au total. On en retourne donc 10 puisque c'est plus grand.

Exemple 2 :

• Entrée : piles = [1,2,3,4,5,100]
• Sortie : 104

Contraintes :

• 1 <= piles.length <= 100
• 1 <= piles[i] <= 10⁴

Indice :

1. Utiliser la programmation dynamique : les états sont (i, m) pour la réponse de piles[i:] et celle donnée m.

Solution :

Nous devons utiliser la programmation dynamique pour trouver le nombre maximum de pierres qu'Alice peut obtenir si les deux joueurs jouent de manière optimale. Voici une approche étape par étape pour développer la solution :

1. Définir l'État et la transition :

   • Définissez un tableau DP 2D où dp[i][m] représente le maximum de pierres qu'Alice peut collecter à partir de la pile i avec une limite de sélection maximale m.
   • Utilisez un tableau de somme de préfixes pour calculer efficacement la somme des pierres dans des sous-tableaux.

2. Cas de base :

   • S'il ne reste plus de pierres à cueillir, le score est de 0.

3. Cas récursif :

   • Pour chaque pile i et sélection maximale autorisée m, calculez le maximum de pierres qu'Alice peut collecter en considérant tous les mouvements possibles (en prenant des piles de 1 à 2 m).

4. Fonction de transition :

   • Pour chaque nombre possible de piles qu'Alice peut choisir, calculez le nombre total de pierres qu'Alice peut obtenir et utilisez les résultats des états futurs pour décider du mouvement optimal.

Implémentons cette solution en PHP : 1140. Jeu de pierre II

stoneGameII($piles1) . "\n"; // Output: 10
echo $solution->stoneGameII($piles2) . "\n"; // Output: 104
?>






  
  
  Explication:




Calcul de la somme des préfixes : Cela permet de calculer rapidement la somme des pierres de n'importe quelle pile i à j.

Initialisation du tableau DP : dp[i][m] contient le maximum de pierres qu'Alice peut obtenir à partir de la pile i avec une limite de sélection maximale de m.

 Transition de programmation dynamique : Pour chaque pile et m, calculez le nombre maximum de pierres qu'Alice peut collecter en itérant sur le nombre de piles possible qu'elle peut prendre et en mettant à jour le tableau DP en conséquence.


Cette approche garantit que la solution est calculée efficacement, en tirant parti de la programmation dynamique pour éviter les calculs redondants.

Liens de contact

Si vous avez trouvé cette série utile, pensez à donner une étoile au référentiel sur GitHub ou à partager la publication sur vos réseaux sociaux préférés ?. Votre soutien signifierait beaucoup pour moi !

Si vous souhaitez du contenu plus utile comme celui-ci, n'hésitez pas à me suivre :


LinkedIn
GitHub



          

            
  

            
        
Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!