2022-12-22：给定一个数字 n，代表数组的长度， 给定一个数字 m，代表数组每个位置都可以在 1~m 之间选择数字， 所有长度为 n 的数组中，最长递增子序列长度为 3 的数组，叫做达标数组。 返回达标数组的

use std::iter::repeat;fn main() {    println!("功能测试开始");    for n in 4..=8 {        for m in 1..=5 {            let ans1 = number1(n, m);            let ans2 = number2(n, m);            if ans1 != ans2 {                println!("{}", ans1);                println!("{}", ans2);                println!("出错了!");            }        }    }    println!("功能测试结束");}
// 暴力方法// 为了验证fn number1(n: i32, m: i32) -> i32 {    let mut a: Vec<i32> = repeat(0).take(n as usize).collect();    return process1(0, n, m, &mut a);}
fn process1(i: i32, n: i32, m: i32, path: &mut Vec<i32>) -> i32 {    if i == n {        return if length_of_lis(path) == 3 { 1 } else { 0 };    } else {        let mut ans = 0;        for cur in 1..=m {            path[i as usize] = cur;            ans += process1(i + 1, n, m, path);        }        return ans;    }}
fn length_of_lis(arr: &mut Vec<i32>) -> i32 {    if arr.len() == 0 {        return 0;    }    let mut ends: Vec<i32> = repeat(0).take(arr.len()).collect();    ends[0] = arr[0];    let mut right = 0;    let mut max = 1;    for i in 1..arr.len() as i32 {        let mut l = 0;        let mut r = right;        while l <= r {            let mut m = (l + r) / 2;            if arr[i as usize] > ends[m as usize] {                l = m + 1;            } else {                r = m - 1;            }        }        right = get_max(right, l);        ends[l as usize] = arr[i as usize];        max = get_max(max, l + 1);    }    return max;}
fn get_max<T: Clone + Copy + std::cmp::PartialOrd>(a: T, b: T) -> T {    if a > b {        a    } else {        b    }}// i : 当前来到的下标// f、s、t : ends数组中放置的数字！// ? == 0，没放！// n : 一共的长度！// m : 每一位，都可以在1~m中随意选择数字// 返回值：i..... 有几个合法的数组！fn zuo(i: i32, f: i32, s: i32, t: i32, n: i32, m: i32) -> i32 {    if i == n {        return if f != 0 && s != 0 && t != 0 { 1 } else { 0 };    }    // i < n    let mut ans = 0;    for cur in 1..=m {        if f == 0 || f >= cur {            ans += zuo(i + 1, cur, s, t, n, m);        } else if s == 0 || s >= cur {            ans += zuo(i + 1, f, cur, t, n, m);        } else if t == 0 || t >= cur {            ans += zuo(i + 1, f, s, cur, n, m);        }    }    return ans;}
// 正式方法// 需要看最长递增子序列！// 尤其是理解ends数组的意义！fn number2(n: i32, m: i32) -> i32 {    //repeat(vec![]).take((m+1) as usize).collect();    let mut dp: Vec<Vec<Vec<Vec<i32>>>> = repeat(        repeat(            repeat(repeat(-1).take((m + 1) as usize).collect())                .take((m + 1) as usize)                .collect(),        )        .take((m + 1) as usize)        .collect(),    )    .take(n as usize)    .collect();    return process2(0, 0, 0, 0, n, m, &mut dp);}
fn process2(    i: i32,    f: i32,    s: i32,    t: i32,    n: i32,    m: i32,    dp: &mut Vec<Vec<Vec<Vec<i32>>>>,) -> i32 {    if i == n {        return if f != 0 && s != 0 && t != 0 { 1 } else { 0 };    }    if dp[i as usize][f as usize][s as usize][t as usize] != -1 {        return dp[i as usize][f as usize][s as usize][t as usize];    }    let mut ans = 0;    for cur in 1..=m {        if f == 0 || cur <= f {            ans += process2(i + 1, cur, s, t, n, m, dp);        } else if s == 0 || cur <= s {            ans += process2(i + 1, f, cur, t, n, m, dp);        } else if t == 0 || cur <= t {            ans += process2(i + 1, f, s, cur, n, m, dp);        }    }    dp[i as usize][f as usize][s as usize][t as usize] = ans;    return ans;}