Để nhân hai ma trận cấp và cấp ta mất phép nhân. Phép nhân ma trận không có tính chất giao hoán nhưng có tính chất kết hợp, tức là . Như vậy để nhân một dãy các ma trận liên tiếp (ma trận sau có số hàng bằng số cột của ma trận trước) chúng ta có thể thực hiện theo thứ tự khác nhau và do đó số phép nhân cần tính cũng khác nhau.
Chẳng hạn ta có ma trận có số chiều lần lượt là: .
Nếu thực hiện theo thứ tự thì số phép nhân cần tính là:
Nếu thực hiện theo thứ tự thì số phép nhân cần tính là :
Yêu cầu: Cho dãy ma trận (ma trận sau có số dòng bằng số cột của ma trận trước, theo thứ tự). Hãy tính số phép nhân tối thiểu cần tính để thực hiện nhân dãy các ma trận đó.
Dữ liệu vào:
Dòng đầu chứa số nguyên dương ;
Dòng sau chứa số nguyên dương (ma trận thứ có dòng và cột).
Dữ liệu ra:
Một số nguyên duy nhất là số phép nhân ít nhất cần tính.
