. Somme cible

494. Somme cible

Difficulté :Moyen

Sujets :Array, programmation dynamique, retour en arrière

Vous recevez un tableau de nombres entiers et une cible entière.

Vous souhaitez construire une expression à partir de nombres en ajoutant l'un des symboles ' ' et '-' avant chaque entier en nombres, puis en concaténant tous les entiers.

• Par exemple, si nums = [2, 1], vous pouvez ajouter un ' ' avant 2 et un '-' avant 1 et les concaténer pour construire l'expression " 2-1".

Renvoie le nombre d'expressions différentes que vous pouvez créer, qui sont évaluées comme cibles.

Exemple 1 :

• Entrée : nums = [1,1,1,1,1], cible = 3
• Sortie : 5
• Explication : Il existe 5 façons d'attribuer des symboles pour que la somme des nombres soit la cible 3.
  • -1 1 1 1 1 = 3
  • 1 - 1 1 1 1 = 3
  • 1 1 - 1 1 1 = 3
  • 1 1 1 - 1 1 = 3
  • 1 1 1 1 - 1 = 3

Exemple 2 :

• Entrée : nums = [1], cible = 1
• Sortie : 1

Contraintes :

• 1 <= nums.length <= 20
• 0 <= nums[i] <= 1000
• 0 <= somme(nums[i]) <= 1000
• -1000 <= cible <= 1000

Solution :

Le problème « Somme cible » consiste à créer des expressions utilisant les nombres dans un tableau nums en attribuant un signe ou - à chaque nombre. L’objectif est de calculer combien d’expressions de ce type correspondent à la cible donnée. Ce problème peut être résolu efficacement en utilisant la programmation dynamique ou le retour en arrière.

Points clés

1. Contraintes d'entrée :
   • Longueur du tableau : 1 <= nums.length <= 20
   • Valeurs des éléments : 0 <= nums[i] <= 1000
   • Plage cible : -1000 <= cible <= 1000

2. Sortie :

   • Renvoie le nombre d'expressions évaluées à la cible.

3. Défis :

   • La solution doit gérer à la fois les petites et les grandes valeurs de cible.
   • Gestion efficace de jusqu'à 2²⁰ combinaisons lors de l'utilisation du backtracking.

Approche

Nous pouvons résoudre ce problème en utilisant la Programmation dynamique (transformation de somme de sous-ensembles) ou le Retour en arrière. Ci-dessous, nous utilisons la Programmation dynamique (DP) pour plus d'efficacité.

Observations clés :

1. Si nous divisons les nombres en deux groupes : P (sous-ensemble positif) et N (sous-ensemble négatif), alors : cible = somme (P) - somme (N)

Réorganiser les termes : somme(P) somme(N) = somme(nums)

Soit S la somme du sous-ensemble positif. Puis : S _{= (somme (nombres) cible) / 2}

1. Si (sum(nums) target) % 2 ≠ 0, renvoie 0 car il est impossible de partitionner les sommes.

Planifier

1. Calculez la somme totale des nombres.
2. Vérifiez si l'objectif est réalisable en utilisant la formule pour S . Si invalide, renvoyez 0.
3. Utilisez une approche DP pour trouver le nombre de sous-ensembles en nombres dont la somme est égale à S .

Implémentons cette solution en PHP : 494. Somme cible

<?php
/**
 * @param Integer[] $nums
 * @param Integer $target
 * @return Integer
 */
function findTargetSumWays($nums, $target) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:
$nums = [1, 1, 1, 1, 1];
$target = 3;
echo findTargetSumWays($nums, $target); // Output: 5
?>

Explication:

1. Validation des entrées :

   • On calcule S = (somme(nums) cible) / 2.
   • Si S n'est pas un entier, il est impossible de diviser les nombres en deux sous-ensembles.

2. Logique de programmation dynamique :

   • dp[j] représente le nombre de façons de former une somme j en utilisant les nombres donnés.
   • En commençant par dp[0] = 1, pour chaque nombre en chiffres, nous mettons à jour dp[j] en ajoutant le nombre de façons de former j - num.

3. Résultat :

   • Après avoir traité tous les nombres, dp[S] contient le nombre de façons d'atteindre la somme cible.

Exemple de procédure pas à pas

Entrée : nums = [1, 1, 1, 1, 1], cible = 3

1. somme totale = 5, S = (5 3) / 2 = 4.
2. Initialiser le tableau DP : dp = [1, 0, 0, 0, 0].
3. Traitez chaque numéro :
   • Pour 1 : Mettre à jour dp : [1, 1, 0, 0, 0].
   • Pour 1 : Mettre à jour dp : [1, 2, 1, 0, 0].
   • Pour 1 : Mettre à jour dp : [1, 3, 3, 1, 0].
   • Pour 1 : Mettre à jour dp : [1, 4, 6, 4, 1].
   • Pour 1 : Mettre à jour dp : [1, 5, 10, 10, 5].
4. Résultat : dp[4] = 5.

Complexité temporelle

• Temps : O(n x S), où n est la longueur des nombres et S est la somme cible.
• Espace : O(S) pour le tableau DP.

Sortie pour exemple

Entrée : nums = [1,1,1,1,1], cible = 3

Sortie : 5

Cette approche calcule efficacement le nombre de façons de former la somme cible à l'aide de la programmation dynamique. En réduisant le problème à une somme de sous-ensembles, nous exploitons la structure de DP pour de meilleures performances.

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!