2022-08-16：绳子总长度为M， 100 -＞ M， (6, 100) (7,23) (10,34) -＞ arr

2022-08-16：绳子总长度为M， 100 -> M， (6, 100) (7,23) (10,34) -> arr， 每一个长度的绳子对应一个价格，比如(6, 10)表示剪成长度为6的绳子，对应价格10， 可以重复切出某个长度的绳子。 定义递归如下： 所有可以切出来的长度 对应 价值都在数组ropes里， ropes[i] = {6, 10} 代表i方案为：切出长度为6的绳子，可以卖10元， index....所有的方案，随便选择。index之前的方案，不能选择， 返回最大的价值。 自己去改动态规划， arr[i][0] -> i号方案能切多少长度， arr[i][1] -> 切出来这个长度，就能获得的价值， arr[index....]自由选择，绳子还剩restLen长度。 返回，最大价值。

答案2022-08-16：

递归。

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

fn main() {
    let mut arr: Vec<Vec<i32>> = vec![vec![6, 10], vec![7, 12]];
    let ans1 = max_value(&mut arr, 0, 19);
    println!("ans1 = {}", ans1);
}

fn max_value(arr: &mut Vec<Vec<i32>>, index: i32, rest_len: i32) -> i32 {
    if rest_len <= 0 || index == arr.len() as i32 {
        return 0;
    }
    // 绳子还有剩余、且还有方案
    // index号方案
    // 不选
    let p1 = max_value(arr, index + 1, rest_len);
    // 选
    let mut p2 = 0;
    if arr[index as usize][0] <= rest_len {
        // 剩余绳子够长，才能选当前方案
        p2 = arr[index as usize][1] + max_value(arr, index, rest_len - arr[index as usize][0]);
    }
    return get_max(p1, p2);
}

fn get_max<T: Clone + Copy + std::cmp::PartialOrd>(a: T, b: T) -> T {
    if a > b {
        a
    } else {
        b
    }
}

执行结果如下：

左神java代码