dp[i][j] = custo mínimo de multiplicar Ai...Aj
dp[i][j] = min(dp[i][k] + dp[k+1][j] + p[i-1]*p[k]*p[j]) para i <= k < j

Matrizes: A1(10x30), A2(30x5), A3(5x60)
Dimensões p = [10, 30, 5, 60]

Opção 1: (A1 x A2) x A3
  A1 x A2 = 10*30*5 = 1500 operações → resultado 10x5
  (A1A2) x A3 = 10*5*60 = 3000 operações
  Total = 4500

Opção 2: A1 x (A2 x A3)
  A2 x A3 = 30*5*60 = 9000 operações → resultado 30x60
  A1 x (A2A3) = 10*30*60 = 18000 operações
  Total = 27000

Tabela dp (preenchida por diagonais):
  dp[1][1]=0  dp[2][2]=0  dp[3][3]=0
  dp[1][2]=1500  dp[2][3]=9000
  dp[1][3]=4500  (melhor: k=1, ou seja (A1)(A2 x A3))

Ordem ótima: (A1 x A2) x A3 → 4500 operações (6x menos!)

const std = @import("std");
const Allocator = std.mem.Allocator;

const INF: u64 = std.math.maxInt(u64) / 2;

pub const ResultadoMCM = struct {
    custo_minimo: u64,
    parentizacao: []u8,
    allocator: Allocator,

    pub fn deinit(self: *ResultadoMCM) void {
        self.allocator.free(self.parentizacao);
    }
};

/// Resolve o problema da multiplicação em cadeia de matrizes.
/// p[i-1] x p[i] são as dimensões da i-ésima matriz.
pub fn matrixChain(allocator: Allocator, p: []const u32) !ResultadoMCM {
    const n = p.len - 1; // número de matrizes

    // dp[i][j] = custo mínimo de multiplicar matrizes i..j
    const dp = try allocator.alloc([]u64, n);
    defer {
        for (dp) |row| allocator.free(row);
        allocator.free(dp);
    }
    const split = try allocator.alloc([]usize, n);
    defer {
        for (split) |row| allocator.free(row);
        allocator.free(split);
    }

    for (0..n) |i| {
        dp[i] = try allocator.alloc(u64, n);
        split[i] = try allocator.alloc(usize, n);
        @memset(dp[i], 0);
        @memset(split[i], 0);
    }

    // Preenche por comprimento da cadeia
    var comprimento: usize = 2;
    while (comprimento <= n) : (comprimento += 1) {
        var i: usize = 0;
        while (i <= n - comprimento) : (i += 1) {
            const j = i + comprimento - 1;
            dp[i][j] = INF;
            var k: usize = i;
            while (k < j) : (k += 1) {
                const custo = dp[i][k] + dp[k + 1][j] +
                    @as(u64, p[i]) * @as(u64, p[k + 1]) * @as(u64, p[j + 1]);
                if (custo < dp[i][j]) {
                    dp[i][j] = custo;
                    split[i][j] = k;
                }
            }
        }
    }

    // Reconstrói parentização
    var buf = std.ArrayList(u8).init(allocator);
    try construirParentizacao(&buf, split, 0, n - 1);

    return .{
        .custo_minimo = dp[0][n - 1],
        .parentizacao = try buf.toOwnedSlice(),
        .allocator = allocator,
    };
}

fn construirParentizacao(buf: *std.ArrayList(u8), split: [][]usize, i: usize, j: usize) !void {
    if (i == j) {
        try buf.append('A');
        // Converte índice para caractere
        if (i + 1 < 10) {
            try buf.append(@intCast('0' + i + 1));
        } else {
            try buf.append('?');
        }
        return;
    }
    try buf.append('(');
    try construirParentizacao(buf, split, i, split[i][j]);
    try buf.appendSlice(" x ");
    try construirParentizacao(buf, split, split[i][j] + 1, j);
    try buf.append(')');
}

pub fn main() !void {
    const stdout = std.io.getStdOut().writer();
    var gpa = std.heap.GeneralPurposeAllocator(.{}){};
    defer _ = gpa.deinit();
    const allocator = gpa.allocator();

    // Exemplo 1: 3 matrizes
    {
        const p = [_]u32{ 10, 30, 5, 60 };
        var resultado = try matrixChain(allocator, &p);
        defer resultado.deinit();

        try stdout.print("Matrizes: A1(10x30), A2(30x5), A3(5x60)\n", .{});
        try stdout.print("Custo mínimo: {d} multiplicações\n", .{resultado.custo_minimo});
        try stdout.print("Parentização: {s}\n\n", .{resultado.parentizacao});
    }

    // Exemplo 2: 4 matrizes
    {
        const p = [_]u32{ 40, 20, 30, 10, 30 };
        var resultado = try matrixChain(allocator, &p);
        defer resultado.deinit();

        try stdout.print("Matrizes: A1(40x20), A2(20x30), A3(30x10), A4(10x30)\n", .{});
        try stdout.print("Custo mínimo: {d} multiplicações\n", .{resultado.custo_minimo});
        try stdout.print("Parentização: {s}\n", .{resultado.parentizacao});
    }
}