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
Entrée :
dimensions = [10, 30, 5, 60]
Sortie attendue :
expected = 4500Entré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.
Entrée :
dimensions = [5, 10]
Sortie attendue :
expected = 0Entré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.