Определение возможности умножения матриц

Вот интересная проблема, с которой я столкнулся на соревновании по программированию:

Постановка задачи: Учитывая размерность n матриц, определите, есть ли существует такой порядок, что матрицы можно умножать. Если он существует, распечатайте размер (произведение размеров) полученной матрицы.

Мои наблюдения: Это сводится к проблеме NP-полного гамильтонова пути, если вы рассматриваете каждую матрицу как вершину и рисуете направленное ребро между матрицами, которые можно умножать. Я решил это простым перебором, но это явно очень медленно. Мне было интересно, есть ли какие-нибудь умные оптимизации для этого конкретного случая проблемы.