package cap4

import (
	"math"
)

// Ex26 矩阵连乘，p为矩阵链，p[0],p[1]代表第一个矩阵的行数和列数，p[1],p[2]代表第二个矩阵的行数和列数
func Ex26(p []int) (int, [][]int) {
	length := len(p)

	m, s := _makeMatrix(length, length), _makeMatrix(length, length)

	for i := 1; i < length; i++ {
		m[i][i] = 0
	}

	n := length - 1
	for l := 2; l <= n; l++ {
		for i := 1; i <= n-l+1; i++ {
			j := i + l - 1
			m[i][j] = math.MaxInt32
			for k := i; k <= j-1; k++ {
				q := m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j]
				if q < m[i][j] {
					m[i][j], s[i][j] = q, k
				}
			}
		}
	}
	return m[1][length-1], s
}