Go/dynamic/matrixmultiplication.go at master · gitgitcode/Go · GitHub

History

54 lines (46 loc) · 1.16 KB

Raw

// matrix chain multiplication problem

// https://en.wikipedia.org/wiki/Matrix_chain_multiplication

// www.geeksforgeeks.org/dynamic_programming-set-8-matrix-chain-multiplication/

package dynamic

import "github.com/TheAlgorithms/Go/math/min"

// MatrixChainRec function

func MatrixChainRec(D []int, i, j int) int {

// d[i-1] x d[i] : dimension of matrix i

if i == j {

return 0

}

q := 1 << 32

for k := i; k < j; k++ {

prod := MatrixChainRec(D, i, k) + MatrixChainRec(D, k+1, j) + D[i-1]*D[k]*D[j]

q = min.Int(prod, q)

}

return q

}

// MatrixChainDp function

func MatrixChainDp(D []int) int {

// d[i-1] x d[i] : dimension of matrix i

N := len(D)

dp := make([][]int, N) // dp[i][j] = matrixChainRec(D, i, j)

for i := 0; i < N; i++ {

dp[i] = make([]int, N)

dp[i][i] = 0

}

for l := 2; l < N; l++ {

for i := 1; i < N-l+1; i++ {

j := i + l - 1

dp[i][j] = 1 << 31

for k := i; k < j; k++ {

prod := dp[i][k] + dp[k+1][j] + D[i-1]*D[k]*D[j]

dp[i][j] = min.Int(prod, dp[i][j])

}

return dp[1][N-1]

}

func main() {

D := []int{2, 2, 2, 2, 2} // 4 matrices

fmt.Print(matrixChainRec(D, 1, 4), "\n")

fmt.Print(matrixChainDp(D), "\n")

}

Go/dynamic/matrixmultiplication.go at master · gitgitcode/Go · GitHub

Expand file tree

Breadcrumbs

matrixmultiplication.go

Latest commit

History

Breadcrumbs

matrixmultiplication.go

File metadata and controls