有长度为length（0<length≤100000)的一个括号序列...

Question

有长度为length（0<length≤100000)的一个括号序列sequence，只有“（”或者“）”两种字符，每个括号的左右两边都能插一个括号，总共有length+1个位置可以插入括号，在第i个位置插入任意括号的代价是cost[i](0<cost[i]≤10000)同一个位置只能插入一个括号，求使得括号序列合法的最小代价，并给出解法的时间复杂度和空间复杂度。

例如输入length=6,sequence="()))((",cost=[1,2,5,5,3,4,1],输出8.

// C/C++
public int getMinimumCost(int length, char[] sequence, int cost[]) {
       // TODO
}

// Java
public int getMinimumCost(int length, List<Character> sequence, List<Integer> cost) {
       //TODO
}