2022-11-30：小红拿到了一个仅由 r、e、d 组成的字符串 她定义一个字符 e 为“好 e“ : 当且仅当这个 e 字符和 r、d 相邻 例如“reeder“只有一个“好 e“，前两个 e 都不是“好 e“，只有第三个

use std::iter::repeat;
fn main() {    let str = "rrredrr";    let ans = min_cost(str); //dereder    println!("ans = {}", ans);}
fn min_cost(str: &str) -> i32 {    let n = str.len() as i32;    if n < 3 {        return -1;    }    let mut arr: Vec<i32> = repeat(0).take(n as usize).collect();    // d认为是0，e认为是1，r认为是2    let strc: Vec<char> = str.chars().collect();    for i in 0..n {        let cur = strc[i as usize];        if cur == 'd' {            arr[i as usize] = 0;        } else if cur == 'e' {            arr[i as usize] = 1;        } else {            arr[i as usize] = 2;        }    }    // 通过上面的转化，问题变成了：    // 1的左右，一定要被0和2包围，这个1才是"好1"    // 请让"好1"的尽量多，返回最少的修改代价    let mut max_good = 0;    let mut min_cost = i32::MAX;    for prepre in 0..3 {        for pre in 0..3 {            let mut cost = if arr[0] == prepre { 0 } else { 1 };            cost += if arr[1] == pre { 0 } else { 1 };            let cur = process(&mut arr, 2, prepre, pre);            if cur.max_good > max_good {                max_good = cur.max_good;                min_cost = cur.min_cost + cost;            } else if cur.max_good == max_good {                min_cost = get_min(min_cost, cur.min_cost + cost);            }        }    }    return min_cost;}
fn get_min<T: Clone + Copy + std::cmp::PartialOrd>(a: T, b: T) -> T {    if a < b {        a    } else {        b    }}struct Info {    max_good: i32,    min_cost: i32,}
impl Info {    fn new(a: i32, b: i32) -> Self {        Self {            max_good: a,            min_cost: b,        }    }}// 暴力递归// 可以自己改成动态规划// arr[index-2]位置的数值是prepre// arr[index-1]位置的数值是pre// 在这种情况下，请让arr[index...]上的好1尽量多// 返回:// 尽量多的"好1"，是多少？// 得到尽量多的"好1"，最小代价是多少?fn process(arr: &mut Vec<i32>, index: i32, prepre: i32, pre: i32) -> Info {    if index == arr.len() as i32 {        return Info::new(0, 0);    }    // 可能性1，arr[index]，变成0    let mut p1_value = if prepre == 2 && pre == 1 { 1 } else { 0 };    let mut p1_cost = if arr[index as usize] == 0 { 0 } else { 1 };    let mut info = process(arr, index + 1, pre, 0);    p1_value += info.max_good;    p1_cost += info.min_cost;    // 可能性2，arr[index]，变成1    let mut p2_value = 0;    let mut p2_cost = if arr[index as usize] == 1 { 0 } else { 1 };    info = process(arr, index + 1, pre, 1);    p2_value += info.max_good;    p2_cost += info.min_cost;    // 可能性3，arr[index]，变成2    let mut p3_value = if prepre == 0 && pre == 1 { 1 } else { 0 };    let mut p3_cost = if arr[index as usize] == 2 { 0 } else { 1 };    info = process(arr, index + 1, pre, 2);    p3_value += info.max_good;    p3_cost += info.min_cost;    // 开始决策，选出三种可能性中的最优解    let mut max_good = 0;    let mut min_cost = i32::MAX;    if p1_value > max_good {        max_good = p1_value;        min_cost = p1_cost;    } else if p1_value == max_good {        min_cost = get_min(min_cost, p1_cost);    }    if p2_value > max_good {        max_good = p2_value;        min_cost = p2_cost;    } else if p2_value == max_good {        min_cost = get_min(min_cost, p2_cost);    }    if p3_value > max_good {        max_good = p3_value;        min_cost = p3_cost;    } else if p3_value == max_good {        min_cost = get_min(min_cost, p3_cost);    }    return Info::new(max_good, min_cost);}