2022-12-04：给定一个由 ‘[‘ ，‘]‘，‘(‘，‘)’ 组成的字符串， 请问最少插入多少个括号就能使这个字符串的所有括号左右配对， 例如当前串是 “([[])“，那么插入一个‘]‘即可满足

use std::{iter::repeat, vec};
fn main() {    let s = "(])])(])([([[)[)]](((])][)(]]])([)(]()[((]][)(]]][)(]([)[[([[))[[[[";    let ans = min_add(s);    println!("{}", ans);    let ans = min_add2(s);    println!("{}", ans);}
fn min_add(s: &str) -> i32 {    let mut n = s.len() as i32;    let mut dp: Vec<Vec<i32>> = vec![];    for i in 0..n {        dp.push(vec![]);        for _ in 0..n {            dp[i as usize].push(-1);        }    }    return process(s, 0, s.len() as i32 - 1, &mut dp);}
fn min_add2(s: &str) -> i32 {    let a = min_add_left(s);    let b = min_add_right(s);    if a < b {        a    } else {        b    }}
fn min_add_left(s: &str) -> i32 {    let sc: Vec<char> = s.chars().collect();    let mut stack: Vec<char> = vec![];    let mut ans = 0;    for c in sc.iter() {        if *c == ']' || *c == ')' {            loop {                if stack.len() == 0 {                    ans += 1;                    break;                }                if *c == ']' {                    if stack[stack.len() - 1] == '[' {                        stack.pop();                        break;                    }
                    ans += 1;                    stack.pop();                } else if *c == ')' {                    if stack[stack.len() - 1] == '(' {                        stack.pop();                        break;                    }
                    ans += 1;                    stack.pop();                }            }        } else if *c == '[' || *c == '(' {            stack.push(*c);        }    }    ans + stack.len() as i32}
fn min_add_right(s: &str) -> i32 {    let mut sc: Vec<char> = s.chars().collect();    sc.reverse();    let mut stack: Vec<char> = vec![];    let mut ans = 0;    for c in sc.iter() {        if *c == '[' || *c == '(' {            loop {                if stack.len() == 0 {                    ans += 1;                    break;                }                if *c == '[' {                    if stack[stack.len() - 1] == ']' {                        stack.pop();                        break;                    }                    ans += 1;                    stack.pop();                } else if *c == '(' {                    if stack[stack.len() - 1] == ')' {                        stack.pop();                        break;                    }                    ans += 1;                    stack.pop();                }            }        } else if *c == ']' || *c == ')' {            stack.push(*c);        }    }    ans + stack.len() as i32}
// 让s[l...r]都完美匹配// 至少需要加几个字符fn process(s: &str, l: i32, r: i32, dp: &mut Vec<Vec<i32>>) -> i32 {    // 只有一个字符，不管是什么，要想配对，都需要添加一个字符    if l == r {        return 1;    }    // 只有两个字符，    // 如果是()、[]，那什么也不需要添加    // 否则，都需要添加2个字符    let sc: Vec<char> = s.chars().collect();    if l == r - 1 {        if (sc[l as usize] == '(' && sc[r as usize] == ')')            || (sc[l as usize] == '[' && sc[r as usize] == ']')        {            return 0;        }        return 2;    }    if dp[l as usize][r as usize] != -1 {        return dp[l as usize][r as usize];    }    // 重点是如下的过程    // 可能性1，先搞定l+1...r，然后搞定l    // 比如s[l...r] = ([][]    // 先搞定[][]，需要添加0个，然后搞定(，需要添加1个    // 整体变成([][])搞定    // l....r -> l l+1....r ?    let p1 = 1 + process(s, l + 1, r, dp);    // 可能性2，先搞定l...r-1，然后搞定r    // 和可能性1同理    // l...r -> ? l...r-1 r    let p2 = 1 + process(s, l, r - 1, dp);    // l( ...r) l+1..r-1    // l[    r] l+1..r-1    // 可能性3，s[l]和s[r]天然匹配，需要搞定的就是l+1..r-1    // 比如([[)，搞定中间的[[，就是最优解了    let mut p3 = i32::MAX;    if (sc[l as usize] == '(' && sc[r as usize] == ')')        || (sc[l as usize] == '[' && sc[r as usize] == ']')    {        p3 = process(s, l + 1, r - 1, dp);    }
    // l......r    // l..l   l+1..r    // l..l+1 l+2..r    // l...l+2 l+3..r    // 可能性后续：可能，最优解并不是l....r整体变成最大的嵌套    // 而是，并列关系！    // l....split 先变成合法    // split+1...r 再变成合法    // 是并列的关系！    // 比如(())[[]]    // l...split : (())    // split+1...r : [[]]    // 这种并列关系下，有可能出最优解    // 所以，枚举每一个可能的并列划分点(split)    let mut ans = get_min(p1, get_min(p2, p3));    for split in l..r {        ans = get_min(ans, process(s, l, split, dp) + process(s, split + 1, r, dp));    }    dp[l as usize][r as usize] = ans;    return ans;}
fn get_min<T: Clone + Copy + std::cmp::PartialOrd>(a: T, b: T) -> T {    if a < b {        a    } else {        b    }}