MatrixChainDp function
(D []int)
| 24 | |
| 25 | // MatrixChainDp function |
| 26 | func MatrixChainDp(D []int) int { |
| 27 | // d[i-1] x d[i] : dimension of matrix i |
| 28 | N := len(D) |
| 29 | |
| 30 | dp := make([][]int, N) // dp[i][j] = matrixChainRec(D, i, j) |
| 31 | for i := 0; i < N; i++ { |
| 32 | dp[i] = make([]int, N) |
| 33 | dp[i][i] = 0 |
| 34 | } |
| 35 | |
| 36 | for l := 2; l < N; l++ { |
| 37 | for i := 1; i < N-l+1; i++ { |
| 38 | j := i + l - 1 |
| 39 | dp[i][j] = 1 << 31 |
| 40 | for k := i; k < j; k++ { |
| 41 | prod := dp[i][k] + dp[k+1][j] + D[i-1]*D[k]*D[j] |
| 42 | dp[i][j] = min.Int(prod, dp[i][j]) |
| 43 | } |
| 44 | } |
| 45 | } |
| 46 | |
| 47 | return dp[1][N-1] |
| 48 | } |
| 49 | |
| 50 | /* |
| 51 | func main() { |