2022-12-04：给定一个由 ‘[‘ ，‘]‘，‘(‘，‘)’ 组成的字符串，请问最少插入多少个括号就能使这个字符

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

答案2022-12-04：

递归。很多人会想到栈，在这里行不通的。
可能性1，先搞定l+1…r，然后搞定l。
可能性2，先搞定l…r-1，然后搞定r。
可能性3，s[l]和s[r]天然匹配，需要搞定的就是l+1..r-1。
递归这三种可能性取最小值即可。

代码用rust编写。代码如下：

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
    }
}