Tous les défis
Difficile 1 résolu 100.0 % de réussite

Multiplication en chaîne de matrices

Trouvez l’ordre le moins coûteux pour multiplier une chaîne de matrices.

Ce que vous allez apprendre

  • Définir une DP sur les sous-chaînes
  • Essayer chaque point de coupure
  • Minimiser le coût des multiplications

Problème

La matrice i a pour dimensions dimensions[i] × dimensions[i+1]. Multiplier une matrice de taille p×q par une matrice de taille q×r coûte p·q·r multiplications scalaires. Choisissez où placer les parenthèses afin que le coût total pour multiplier toute la chaîne soit minimal.

Implémentez min_multiplications(dimensions).

Entrée

dimensions : n + 1 tailles décrivant n matrices.

Sortie

Retournez le coût total minimal.

Contraintes

2 ≤ longueur de dimensions ≤ 200 ; 1 ≤ chaque taille ≤ 500

Exemples

Exemple 1
Entrée :
dimensions = [10, 30, 5, 60]

Sortie attendue :
expected = 4500
Entrée :
std::vector<long long> dimensions = {10, 30, 5, 60};

Sortie attendue :
long long expected = 4500;
Entrée :
long[] dimensions = new long[] {10, 30, 5, 60};

Sortie attendue :
long expected = 4500;

Explication

(A×B)×C coûte 10·30·5 + 10·5·60 = 4500, ce qui est moins cher que A×(B×C) = 27000.

Exemple 2
Entrée :
dimensions = [5, 10]

Sortie attendue :
expected = 0
Entrée :
std::vector<long long> dimensions = {5, 10};

Sortie attendue :
long long expected = 0;
Entrée :
long[] dimensions = new long[] {5, 10};

Sortie attendue :
long expected = 0;

Explication

Une seule matrice ne nécessite aucune multiplication : 0.

Comment l'aborder

Essayez d'abord seul, puis ouvrez les indices un par un.

Indice 1

L’ordre de multiplication change le coût total même si la forme finale de la matrice reste la même.

Indice 2

Essaie chaque point de coupe possible pour chaque intervalle et réutilise les résultats des plus petits intervalles.

Indice 3

Utilise l’array des dimensions avec soin : chaque sous-problème dépend des bornes autour des matrices, pas seulement du nombre de matrices.

Complexité attendue

temps O(n^3), espace supplémentaire O(n^2)

Références

Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.

La meilleure solution validée de chaque codeur. Les plus rapides, les plus légères et les mieux notées passent devant.

# Codeur Langage Temps Mémoire Note de l'IA Solution
1 ННикита Python 777 ms - 5/5 Voir le code

Apprenez des autres

Solutions de la communauté

Attention spoiler : 1 solution complète ci-dessous Essayez d'abord de le résoudre vous-même. Vous pouvez toujours jeter un œil au code des autres développeurs et aux avis IA. Connectez-vous et résolvez le défi pour rejoindre la discussion.