42 lines
1.1 KiB
Go
42 lines
1.1 KiB
Go
package algo
|
|
|
|
func DP(t1 []int, t2 []int, e1 []int, e2 []int) int {
|
|
Len := len(t1)
|
|
if len(t2) != Len || len(e1) != Len || len(e2) != Len {
|
|
return -1
|
|
}
|
|
dp1 := make([]int, Len)
|
|
dp2 := make([]int, Len)
|
|
dp1[0], dp2[0] = t1[0], t2[0]
|
|
|
|
for i := 1; i < Len; i++ {
|
|
dp1[i] = min(dp1[i-1], dp2[i-1]+e2[i-1]) + t1[i]
|
|
dp2[i] = min(dp2[i-1], dp1[i-1]+e1[i-1]) + t2[i]
|
|
}
|
|
|
|
return min(dp1[Len-1], dp2[Len-1])
|
|
}
|
|
|
|
func Rec(t1 []int, t2 []int, e1 []int, e2 []int) int {
|
|
Len := len(t1)
|
|
if len(t2) != Len || len(e1) != Len || len(e2) != Len {
|
|
return -1
|
|
}
|
|
|
|
return min(rec(t1, t2, e1, e2))
|
|
}
|
|
|
|
func rec(t1 []int, t2 []int, e1 []int, e2 []int) (int, int, int, int) {
|
|
Len := len(t1)
|
|
if Len == 1 {
|
|
return t1[0], 0x3f3f3f3f3f3f3f3f, 0x3f3f3f3f3f3f3f3f, t2[0]
|
|
}
|
|
mid := Len / 2
|
|
a11, a12, a21, a22 := rec(t1[:mid], t2[:mid], e1[:mid], e2[:mid])
|
|
b11, b12, b21, b22 := rec(t1[mid:], t2[mid:], e1[mid:], e2[mid:])
|
|
s1 := e1[mid-1]
|
|
s2 := e2[mid-1]
|
|
return min(a11+b11, a11+s1+b21, a12+s2+b11, a12+b21), min(a11+b12, a11+s1+b22, a12+s2+b12, a12+b22),
|
|
min(a21+b11, a21+s1+b21, a22+b21, a22+s2+b11), min(a21+b12, a21+s1+b22, a22+b22, a22+s2+b12)
|
|
}
|