Multiplication en chaîne de matrices

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 = 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;

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;

Références

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

• Wikipedia: Matrix chain multiplication