2022-11-20：小团生日收到妈妈送的两个一模一样的数列作为礼物！ 他很开心的把玩，不过不小心没拿稳将数列摔坏了！ 现在他手上的两个数列分别为 A 和 B，长度分别为 n 和 m。 小团很想再次让这两个数列变

use std::iter::repeat;
fn main() {    let mut nums1 = vec![2, 1000, 2000];    let mut nums2 = vec![999, 1, 2003];    let ans = min_cost(&mut nums1, &mut nums2);    println!("ans = {:?}", ans);}
// A B// zuo(A,B,0,0)// A[ai.....] 对应 B[bi.....]// 请变一样// 返回最小代价fn zuo(aa: &mut Vec<i32>, bb: &mut Vec<i32>, ai: i32, bi: i32) -> i32 {    if ai == aa.len() as i32 && bi == bb.len() as i32 {        return 0;    }    if ai != aa.len() as i32 && bi == bb.len() as i32 {        return aa[ai as usize] + zuo(aa, bb, ai + 1, bi);    }    if ai == aa.len() as i32 && bi != bb.len() as i32 {        return bb[bi as usize] + zuo(aa, bb, ai, bi + 1);    }    // A[ai] 有数 B[bi] 有数    // 可能性1 ： 删掉A[ai]    let p1 = aa[ai as usize] + zuo(aa, bb, ai + 1, bi);    // 可能性2 ： 删掉B[bi]    let p2 = bb[bi as usize] + zuo(aa, bb, ai, bi + 1);    // 可能性3 ： 同时删掉    // int p3 = A[ai] + B[bi] + zuo(A, B, ai + 1, bi + 1);    // 可能性4 ： 变！A[ai] -> B[bi] B[bi] -> A[ai]    let p4 = if aa[ai as usize] >= bb[bi as usize] {        aa[ai as usize] - bb[bi as usize]    } else {        bb[ai as usize] - aa[bi as usize]    } + zuo(aa, bb, ai + 1, bi + 1);    // 可能性5 ： A[ai] == B[bi]    return get_min(p1, get_min(p2, p4));}
fn get_min<T: Clone + Copy + std::cmp::PartialOrd>(a: T, b: T) -> T {    if a < b {        a    } else {        b    }}
fn min_cost(aa: &mut Vec<i32>, bb: &mut Vec<i32>) -> i32 {    let n = aa.len() as i32;    let m = bb.len() as i32;    let mut dp: Vec<Vec<i32>> = repeat(repeat(-1).take((m + 1) as usize).collect())        .take((n + 1) as usize)        .collect();    return change2(aa, bb, 0, 0, &mut dp);}
// 暴力递归// A[indexA....]和B[indexB....]完全一样// 需要付出最少的代价返回fn change(aa: &mut Vec<i32>, bb: &mut Vec<i32>, index_a: i32, index_b: i32) -> i32 {    if index_a == aa.len() as i32 && index_b == bb.len() as i32 {        return 0;    }    if index_a == aa.len() as i32 && index_b != bb.len() as i32 {        return bb[index_b as usize] + change(aa, bb, index_a, index_b + 1);    }    if index_a != aa.len() as i32 && index_b == bb.len() as i32 {        return aa[index_a as usize] + change(aa, bb, index_a + 1, index_b);    }    // indexA、indexB都没到最后    // 可能性1，丢掉A[indexA]    let p1 = aa[index_a as usize] + change(aa, bb, index_a + 1, index_b);    // 可能性2，丢掉B[indexB]    let p2 = bb[index_b as usize] + change(aa, bb, index_a, index_b + 1);    // 可能性3，同时丢掉A[indexA]、B[indexB]    // 可能性4，把A[indexA]改成B[indexB](也是B[indexB]改成A[indexA]，因为代价一样)    // 可能性5，A[indexA]本来就是等于B[indexB]的，改的代价为0    // 可以分析出可能性3，肯定是不如可能性4、可能性5的    // 所以舍弃掉可能性3    let p45 = if aa[index_a as usize] - bb[index_b as usize] > 0 {        aa[index_a as usize] - bb[index_b as usize]    } else {        bb[index_b as usize] - aa[index_a as usize]    } + change(aa, bb, index_a + 1, index_b + 1);    return get_min(get_min(p1, p2), p45);}
// 上面的暴力递归方法改动态规划fn change2(    aa: &mut Vec<i32>,    bb: &mut Vec<i32>,    index_a: i32,    index_b: i32,    dp: &mut Vec<Vec<i32>>,) -> i32 {    if index_a == aa.len() as i32 && index_b == bb.len() as i32 {        return 0;    }    if dp[index_a as usize][index_b as usize] != -1 {        return dp[index_a as usize][index_b as usize];    }    let mut ans = 0;    if index_a == aa.len() as i32 && index_b != bb.len() as i32 {        ans = bb[index_b as usize] + change2(aa, bb, index_a, index_b + 1, dp);    } else if index_a != aa.len() as i32 && index_b == bb.len() as i32 {        ans = aa[index_a as usize] + change2(aa, bb, index_a + 1, index_b, dp);    } else {        let p1 = aa[index_a as usize] + change2(aa, bb, index_a + 1, index_b, dp);        let p2 = bb[index_b as usize] + change2(aa, bb, index_a, index_b + 1, dp);        let p45 = if aa[index_a as usize] - bb[index_b as usize] > 0 {            aa[index_a as usize] - bb[index_b as usize]        } else {            bb[index_b as usize] - aa[index_a as usize]        } + change2(aa, bb, index_a + 1, index_b + 1, dp);        ans = get_min(get_min(p1, p2), p45);    }    dp[index_a as usize][index_b as usize] = ans;    return ans;}