---
title: "Multiplicação de Cadeia de Matrizes"
url: "https://rustlang.com.br/algoritmos/matrix-chain/"
markdown_url: "https://rustlang.com.br/algoritmos/matrix-chain.MD"
description: "Resolva a multiplicação de cadeia de matrizes em Rust com DP: parentetização ótima, preenchimento diagonal da tabela e reconstrução da ordem."
date: "2026-02-24"
author: "Equipe Rust Brasil"
---

# Multiplicação de Cadeia de Matrizes

Resolva a multiplicação de cadeia de matrizes em Rust com DP: parentetização ótima, preenchimento diagonal da tabela e reconstrução da ordem.


O problema da **Multiplicação de Cadeia de Matrizes** (Matrix Chain Multiplication) pergunta: dada uma sequência de matrizes a serem multiplicadas, qual a ordem de parentetização que minimiza o número total de operações escalares? A multiplicação de matrizes é associativa --- `(AB)C = A(BC)` --- mas a ordem dos parênteses pode fazer uma diferença **enorme** no custo computacional.

Este problema aparece em otimização de consultas em bancos de dados (planos de execução), compiladores (otimização de expressões), computação gráfica (transformações encadeadas) e qualquer sistema que precise encadear operações com custos variáveis.

## O Problema

**Entrada**: Uma sequência de `n` matrizes `A_1, A_2, ..., A_n`, onde a matriz `A_i` tem dimensões `p[i-1] x p[i]`.

**Objetivo**: Determinar a parentetização que minimiza o número total de multiplicações escalares.

**Exemplo:**

```
Matrizes: A(10x30), B(30x5), C(5x60)
Dimensões: p = [10, 30, 5, 60]

Ordem 1: (AB)C
  AB: 10*30*5 = 1500 operações  ->  resultado 10x5
  (AB)C: 10*5*60 = 3000 operações
  Total: 1500 + 3000 = 4500

Ordem 2: A(BC)
  BC: 30*5*60 = 9000 operações  ->  resultado 30x60
  A(BC): 10*30*60 = 18000 operações
  Total: 9000 + 18000 = 27000

Ordem ótima: (AB)C com 4500 operações (6x mais eficiente!)
```

## Abordagem Ingênua (Força Bruta)

O número de parentetizações possíveis é dado pelos números de Catalan: `C(n-1) = (2(n-1))! / (n! * (n-1)!)`, que cresce exponencialmente. Para 4 matrizes são 5 formas; para 10 matrizes são 4862; para 20 são mais de 1,7 bilhão.

```rust
/// Força bruta: testa todas as parentetizações.
/// Complexidade: O(2^n) — exponencial (números de Catalan).
fn mcm_bruta(p: &[u64], i: usize, j: usize) -> u64 {
    // Caso base: uma única matriz, custo zero
    if i == j {
        return 0;
    }

    let mut minimo = u64::MAX;

    // Tenta cada ponto de divisão k entre i e j
    for k in i..j {
        let custo = mcm_bruta(p, i, k)          // Custo do lado esquerdo
                  + mcm_bruta(p, k + 1, j)      // Custo do lado direito
                  + p[i - 1] * p[k] * p[j];     // Custo de combinar

        minimo = minimo.min(custo);
    }

    minimo
}

fn main() {
    let p = vec![10, 30, 5, 60];
    let n = p.len() - 1; // 3 matrizes

    println!("Custo mínimo: {}", mcm_bruta(&p, 1, n)); // 4500
}
```

## Identificando Subestrutura Ótima

A recorrência para o custo mínimo de multiplicar as matrizes `A_i ... A_j`:

```
dp[i][j] = 0                                          se i == j
dp[i][j] = min(dp[i][k] + dp[k+1][j] + p[i-1]*p[k]*p[j])  para i <= k < j
```

O ponto de divisão `k` divide a cadeia em dois grupos: `(A_i ... A_k)` e `(A_{k+1} ... A_j)`. O custo de combinar os dois resultados é `p[i-1] * p[k] * p[j]`.

- **Subestrutura ótima**: a parentetização ótima de `A_i..A_j` contém parentetizações ótimas de `A_i..A_k` e `A_{k+1}..A_j`.
- **Subproblemas sobrepostos**: subcadeias são compartilhadas entre diferentes partições.

## Visualização da Tabela DP

A tabela é preenchida **por diagonais** (por comprimento crescente da cadeia).

Para `p = [10, 30, 5, 60]` (matrizes A1(10x30), A2(30x5), A3(5x60)):

```
       j=1      j=2      j=3
     +--------+--------+--------+
i=1  |   0    | 1500   |  4500  |
     +--------+--------+--------+
i=2  |        |   0    |  9000  |
     +--------+--------+--------+
i=3  |        |        |   0    |
     +--------+--------+--------+

Preenchimento por diagonais:

Diagonal 0 (comprimento 1): cadeias de 1 matriz
  dp[1][1] = 0, dp[2][2] = 0, dp[3][3] = 0

Diagonal 1 (comprimento 2): cadeias de 2 matrizes
  dp[1][2]: k=1 -> p[0]*p[1]*p[2] = 10*30*5 = 1500
  dp[2][3]: k=2 -> p[1]*p[2]*p[3] = 30*5*60 = 9000

Diagonal 2 (comprimento 3): cadeia completa
  dp[1][3]: k=1 -> dp[1][1] + dp[2][3] + p[0]*p[1]*p[3]
                  = 0 + 9000 + 10*30*60 = 27000
            k=2 -> dp[1][2] + dp[3][3] + p[0]*p[2]*p[3]
                  = 1500 + 0 + 10*5*60 = 4500   <-- mínimo!
  dp[1][3] = 4500 (k_ótimo = 2, ou seja: (A1*A2)*A3)
```

Para um exemplo maior, `p = [40, 20, 30, 10, 30]` (4 matrizes):

```
       j=1      j=2      j=3      j=4
     +--------+--------+--------+--------+
i=1  |   0    | 24000  | 18000  | 30000  |
     +--------+--------+--------+--------+
i=2  |        |   0    |  6000  | 12000  |
     +--------+--------+--------+--------+
i=3  |        |        |   0    |  9000  |
     +--------+--------+--------+--------+
i=4  |        |        |        |   0    |
     +--------+--------+--------+--------+

dp[1][4] = 30000, parentetização: ((A1(A2*A3))*A4)
```

## Complexidade

| Abordagem | Tempo | Espaço | Observação |
|-----------|-------|--------|------------|
| Força Bruta | O(2^n) Catalan | O(n) pilha | Números de Catalan |
| Top-Down (Memoização) | O(n^3) | O(n^2) | n^2 subproblemas, O(n) cada |
| Bottom-Up (Tabulação) | O(n^3) | O(n^2) | Preenchimento diagonal |
| Otimizado (Hu-Shing) | O(n log n) | O(n) | Algoritmo avançado, raro na prática |

## Implementação: Top-Down (Memoização)

```rust
use std::collections::HashMap;

/// Multiplicação de cadeia de matrizes com memoização.
fn mcm_memo(
    p: &[u64],
    i: usize,
    j: usize,
    cache: &mut HashMap<(usize, usize), u64>,
) -> u64 {
    if i == j {
        return 0;
    }

    if let Some(&valor) = cache.get(&(i, j)) {
        return valor;
    }

    let mut minimo = u64::MAX;

    for k in i..j {
        let custo = mcm_memo(p, i, k, cache)
                  + mcm_memo(p, k + 1, j, cache)
                  + p[i - 1] * p[k] * p[j];
        minimo = minimo.min(custo);
    }

    cache.insert((i, j), minimo);
    minimo
}

fn main() {
    let p = vec![10, 30, 5, 60];
    let n = p.len() - 1;

    let mut cache = HashMap::new();
    let resultado = mcm_memo(&p, 1, n, &mut cache);
    println!("Custo mínimo: {}", resultado); // 4500

    // Exemplo maior
    cache.clear();
    let p2 = vec![40, 20, 30, 10, 30];
    let n2 = p2.len() - 1;
    let resultado2 = mcm_memo(&p2, 1, n2, &mut cache);
    println!("Custo mínimo: {}", resultado2); // 30000
}
```

## Implementação: Bottom-Up (Tabulação)

```rust
/// Multiplicação de cadeia de matrizes com tabulação.
/// Retorna o custo mínimo e a tabela de pontos de divisão.
fn mcm_tabular(p: &[u64]) -> (u64, Vec<Vec<u64>>, Vec<Vec<usize>>) {
    let n = p.len() - 1; // Número de matrizes

    // dp[i][j] = custo mínimo para multiplicar A_i ... A_j
    let mut dp = vec![vec![0u64; n + 1]; n + 1];

    // div[i][j] = ponto de divisão ótimo para dp[i][j]
    let mut div = vec![vec![0usize; n + 1]; n + 1];

    // Preenche por comprimento crescente da cadeia
    for comprimento in 2..=n {
        for i in 1..=n - comprimento + 1 {
            let j = i + comprimento - 1;
            dp[i][j] = u64::MAX;

            // Testa cada ponto de divisão
            for k in i..j {
                let custo = dp[i][k] + dp[k + 1][j] + p[i - 1] * p[k] * p[j];
                if custo < dp[i][j] {
                    dp[i][j] = custo;
                    div[i][j] = k;
                }
            }
        }
    }

    (dp[1][n], dp, div)
}

fn main() {
    let p = vec![10, 30, 5, 60];
    let (custo, _dp, _div) = mcm_tabular(&p);
    println!("Custo mínimo: {}", custo); // 4500

    let p2 = vec![40, 20, 30, 10, 30];
    let (custo2, _dp2, _div2) = mcm_tabular(&p2);
    println!("Custo mínimo: {}", custo2); // 30000

    // Exemplo com 6 matrizes
    let p3 = vec![30, 35, 15, 5, 10, 20, 25];
    let (custo3, _dp3, _div3) = mcm_tabular(&p3);
    println!("Custo mínimo: {}", custo3); // 15125
}
```

## Otimização de Espaço

Diferente de Fibonacci e mochila, a multiplicação de cadeia de matrizes **não pode ser facilmente otimizada para espaço O(n)**. Cada célula `dp[i][j]` pode depender de qualquer célula na mesma linha ou coluna, exigindo a tabela completa O(n^2). O algoritmo de Hu-Shing alcança O(n log n) tempo e O(n) espaço, mas é significativamente mais complexo de implementar.

Para fins práticos, O(n^2) de espaço raramente é um problema --- o gargalo está no tempo O(n^3).

## Reconstruindo a Solução

Para reconstruir a **parentetização ótima**, usamos a tabela `div`:

```rust
/// Reconstrói e imprime a parentetização ótima.
fn imprimir_parentetizacao(div: &[Vec<usize>], i: usize, j: usize) -> String {
    if i == j {
        return format!("A{}", i);
    }

    let k = div[i][j];
    let esquerda = imprimir_parentetizacao(div, i, k);
    let direita = imprimir_parentetizacao(div, k + 1, j);

    format!("({} x {})", esquerda, direita)
}

fn main() {
    let p = vec![10, 30, 5, 60];
    let (custo, _dp, div) = mcm_tabular(&p);
    let parentetizacao = imprimir_parentetizacao(&div, 1, p.len() - 1);
    println!("Custo: {} -> {}", custo, parentetizacao);
    // Custo: 4500 -> ((A1 x A2) x A3)

    let p2 = vec![40, 20, 30, 10, 30];
    let (custo2, _dp2, div2) = mcm_tabular(&p2);
    let par2 = imprimir_parentetizacao(&div2, 1, p2.len() - 1);
    println!("Custo: {} -> {}", custo2, par2);
    // Custo: 30000 -> ((A1 x (A2 x A3)) x A4)

    let p3 = vec![30, 35, 15, 5, 10, 20, 25];
    let (custo3, _dp3, div3) = mcm_tabular(&p3);
    let par3 = imprimir_parentetizacao(&div3, 1, p3.len() - 1);
    println!("Custo: {} -> {}", custo3, par3);
    // Custo: 15125 -> ((A1 x (A2 x A3)) x ((A4 x A5) x A6))
}

fn mcm_tabular(p: &[u64]) -> (u64, Vec<Vec<u64>>, Vec<Vec<usize>>) {
    let n = p.len() - 1;
    let mut dp = vec![vec![0u64; n + 1]; n + 1];
    let mut div = vec![vec![0usize; n + 1]; n + 1];
    for comprimento in 2..=n {
        for i in 1..=n - comprimento + 1 {
            let j = i + comprimento - 1;
            dp[i][j] = u64::MAX;
            for k in i..j {
                let custo = dp[i][k] + dp[k + 1][j] + p[i - 1] * p[k] * p[j];
                if custo < dp[i][j] {
                    dp[i][j] = custo;
                    div[i][j] = k;
                }
            }
        }
    }
    (dp[1][n], dp, div)
}
```

### Exemplo Completo: Multiplicação Real de Matrizes

Para demonstrar que a ordem realmente importa, podemos simular a multiplicação:

```rust
/// Representa uma matriz como Vec<Vec<f64>>.
/// Multiplica duas matrizes e conta as operações escalares.
fn multiplicar(
    a: &Vec<Vec<f64>>,
    b: &Vec<Vec<f64>>,
    ops: &mut u64,
) -> Vec<Vec<f64>> {
    let linhas_a = a.len();
    let colunas_a = a[0].len();
    let colunas_b = b[0].len();

    let mut resultado = vec![vec![0.0; colunas_b]; linhas_a];

    for i in 0..linhas_a {
        for j in 0..colunas_b {
            for k in 0..colunas_a {
                resultado[i][j] += a[i][k] * b[k][j];
                *ops += 1; // Conta cada multiplicação escalar
            }
        }
    }

    resultado
}

fn main() {
    // Matrizes com dimensões 10x30, 30x5, 5x60
    let a = vec![vec![1.0; 30]; 10]; // 10x30
    let b = vec![vec![1.0; 5]; 30];  // 30x5
    let c = vec![vec![1.0; 60]; 5];  // 5x60

    // Ordem 1: (AB)C
    let mut ops1 = 0;
    let ab = multiplicar(&a, &b, &mut ops1);
    let _abc1 = multiplicar(&ab, &c, &mut ops1);
    println!("(AB)C: {} operações", ops1); // 4500

    // Ordem 2: A(BC)
    let mut ops2 = 0;
    let bc = multiplicar(&b, &c, &mut ops2);
    let _abc2 = multiplicar(&a, &bc, &mut ops2);
    println!("A(BC): {} operações", ops2); // 27000

    println!("Razão: {:.1}x mais eficiente", ops2 as f64 / ops1 as f64);
}
```

## Exercícios Práticos

1. **Contagem de parentetizações**: Calcule quantas parentetizações distintas existem para `n` matrizes. Implemente tanto por recursão com memoização quanto pela fórmula dos números de Catalan.

2. **Custo máximo**: Em vez de minimizar, encontre a parentetização que **maximiza** o número de operações. Útil para entender o pior caso.

3. **Cadeia com custos variáveis**: Generalize para o caso onde multiplicar matrizes de dimensões `p x q x r` tem custo `w(p,q,r)` arbitrário (não necessariamente `p*q*r`).

4. **Triangulação de polígono**: O problema da triangulação ótima de um polígono convexo tem a mesma estrutura recursiva. Implemente-o usando a mesma abordagem de DP.

## Veja Também

- [Vec — Vetores dinâmicos](/stdlib/vec/) — base para as matrizes e tabela DP
- [Arrays — Tamanho fixo](/stdlib/arrays/) — alternativa para matrizes de tamanho conhecido
- [Tipos Numéricos](/stdlib/tipos-numericos/) — tipos usados nas dimensões e contagens
- [Fibonacci com DP](/algoritmos/fibonacci-dp/) — introdução a programação dinâmica
- [Problema da Mochila](/algoritmos/knapsack/) — outro clássico de DP com reconstrução
- [Soma de Subconjuntos](/algoritmos/subset-sum/) — outro problema de DP com tabela bidimensional