53 lines
838 B
Go
53 lines
838 B
Go
package algo
|
|
|
|
func DP(arr []int) int {
|
|
n := len(arr) - 1
|
|
if n <= 0 {
|
|
return 0
|
|
}
|
|
|
|
const inf = int(^uint(0) >> 1)
|
|
dp := make([][]int, n)
|
|
for i := range dp {
|
|
dp[i] = make([]int, n)
|
|
}
|
|
|
|
for length := 2; length <= n; length++ {
|
|
for l := 0; l+length-1 < n; l++ {
|
|
r := l + length - 1
|
|
dp[l][r] = inf
|
|
for k := l; k < r; k++ {
|
|
cost := dp[l][k] + dp[k+1][r] + arr[l]*arr[k+1]*arr[r+1]
|
|
if cost < dp[l][r] {
|
|
dp[l][r] = cost
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
return dp[0][n-1]
|
|
}
|
|
|
|
func Greedy(arr []int) int {
|
|
if len(arr) <= 2 {
|
|
return 0
|
|
}
|
|
|
|
dims := append([]int(nil), arr...)
|
|
cost := 0
|
|
|
|
for len(dims) > 2 {
|
|
best := 1
|
|
for i := 2; i < len(dims)-1; i++ {
|
|
if dims[i] > dims[best] {
|
|
best = i
|
|
}
|
|
}
|
|
|
|
cost += dims[best-1] * dims[best] * dims[best+1]
|
|
dims = append(dims[:best], dims[best+1:]...)
|
|
}
|
|
|
|
return cost
|
|
}
|