. Imprimante étrange

664. Imprimante étrange

Difficulté : Difficile

Sujets : Chaîne, programmation dynamique

Il existe une imprimante étrange avec les deux propriétés spéciales suivantes :

• L'imprimante ne peut imprimer qu'une séquence du le même caractère à chaque fois.
• À chaque tour, l'imprimante peut imprimer de nouveaux caractères commençant et se terminant à n'importe quel endroit et couvrira les caractères originaux existants.

Étant donné une chaîne s, renvoie le nombre minimum de tours dont l'imprimante a eu besoin pour l'imprimer.

Exemple 1 :

• Entrée : s = "aaabbb"
• Sortie : 2
• Explication : Imprimez d'abord "aaa" puis imprimez "bbb".

Exemple 2 :

• Entrée : s = "aba"
• Sortie : 2
• Explication : Imprimez d'abord "aaa", puis imprimez "b" à partir de la deuxième place de la chaîne, qui couvrira le caractère "a" existant.

Contraintes :

• 1 <= s.length <= 100
• s se compose de lettres anglaises minuscules.

Solution :

Nous pouvons utiliser la programmation dynamique. L'idée est de minimiser le nombre de tours nécessaires pour imprimer la chaîne en la décomposant en sous-problèmes.

Le problème peut être résolu en utilisant la programmation dynamique. L'idée est de diviser le problème en sous-problèmes plus petits où vous déterminez le nombre de tours minimum requis pour imprimer chaque sous-chaîne de s. On peut tirer parti du constat suivant :

• Si deux caractères adjacents sont identiques, vous pouvez prolonger une opération précédente au lieu de la compter comme une nouvelle opération.

Solution de programmation dynamique

Soit dp[i][j] le nombre minimum de tours requis pour imprimer la sous-chaîne s[i:j+1].

1. Si s[i] == s[j], alors dp[i][j] = dp[i][j-1] car le dernier caractère s[j] peut être imprimé avec l'opération précédente.
2. Sinon, dp[i][j] = min(dp[i][k] + dp[k+1][j]) pour tout i <= k < j.

Implémentons cette solution en PHP : 664. Imprimante étrange

  
  
  Explication:



DP Array : Le tableau 2D dp[i][j] représente le nombre minimum de tours requis pour imprimer la sous-chaîne de l'index i à j.
Initialisation : On initialise dp[i][i] = 1 car un seul caractère peut être imprimé en un seul tour.

Remplir la table DP :


Si les caractères en i et j sont les mêmes ($s[$i] == $s[$j]), alors l'impression de i à j prend le même nombre de tours que l'impression de i à j-1 puisque $s[$j] ​​peut être imprimé dans le même tour que $s[$i].
S'ils sont différents, on essaie de trouver le nombre minimum de tours en divisant la corde en différents points (k).


Résultat : Le nombre minimum de tours requis pour imprimer la chaîne entière est stocké dans dp[0][$n - 1].


Cette solution calcule efficacement le nombre minimum de tours requis pour imprimer la chaîne en considérant toutes les manières possibles de diviser et d'imprimer la chaîne.

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!