2023-03-28:有一根长度为 n 个单位的木棍,棍上从 0 到 n 标记了若干位置

2023-03-28:有一根长度为 n 个单位的木棍,棍上从 0 到 n 标记了若干位置。
给你一个整数数组 cuts ,其中 cuts[i] 表示你需要将棍子切开的位置,
你可以按顺序完成切割,也可以根据需要更改切割的顺序,
每次切割的成本都是当前要切割的棍子的长度,切棍子的总成本是历次切割成本的总和。
对棍子进行切割将会把一根木棍分成两根较小的木棍,
这两根木棍的长度和就是切割前木棍的长度。
返回切棍子的最小总成本。
输入:n = 9, cuts = [5,6,1,4,2]。
输出:22。

答案2023-03-28:

步骤如下:

1.将切割点数组 cuts 排序,并构建新的数组 arr,将 0 和 n 加入其中,得到长度为 m+2 的数组。

2.初始化一个 m+2 行 m+2 列的 DP 数组 dp,dp[i][j] 表示将区间 [i,j] 内的木棍切割成最小块的总成本。初始化值为 -1。

3.定义递归函数 process(arr, l, r, dp),表示计算将 arr[l..r+1] 这段木棍切割成若干小块的最小总成本。

4.在 process 函数中,分三种情况讨论:

当 l > r 时,说明该区间内没有木棍需要切割,返回 0。

当 l == r 时,说明该区间只有一根木棍,成本为该木棍的长度。

当 dp[l][r] != -1 时,说明该区间的最小成本已经被计算过,直接返回结果 dp[l][r]

5.在 process 函数中,枚举所有可能的切割点 k,计算将 arr[l..k] 和 arr[k+1..r+1] 两段木棍切割成最小块的总成本,并加上当前区间的长度(即 arr[r+1]-arr[l-1]),得到该切割点下的总成本。取最小值作为答案。

6.将答案缓存到 dp[l][r] 中,并返回结果。

7.在主函数中,调用 min_cost(n, &cuts) 函数,得到切割最小总成本。

该算法的时间复杂度为 O(n ^ 3),空间复杂度为 O(n ^ 2)。其中,nn 表示初始木棒的长度,即 n 变量的值。

时间复杂度为 O(n ^ 3)。
空间复杂度为 O(n ^ 2)。

rust代码如下:

// 计算给定切割点下的最小成本
fn min_cost(n: i32, cuts: &[i32]) -> i32 {
    let m = cuts.len();
    // 将切割点排序并构建数组
    let mut arr = vec![0; m + 2];
    arr[0] = 0;
    for i in 1..=m {
        arr[i] = cuts[i - 1];
    }
    arr[m + 1] = n;
    // 初始化 DP 数组
    let mut dp = vec![vec![-1; m + 2]; m + 2];
    process(&arr, 1, m, &mut dp)
}

// 递归函数,计算给定区间的最小成本
fn process(arr: &[i32], l: usize, r: usize, dp: &mut Vec<Vec<i32>>) -> i32 {
    // 如果区间为空,则成本为 0
    if l > r {
        return 0;
    }
    // 如果区间只有一个元素,则成本为该元素的长度
    if l == r {
        return arr[r + 1] - arr[l - 1];
    }
    // 如果 DP 数组中已经计算过当前区间的最小成本,则直接返回结果
    if dp[l][r] != -1 {
        return dp[l][r];
    }
    // 枚举所有可能的切割点,计算最小成本
    let mut ans = i32::max_value();
    for k in l..=r {
        ans = min(ans, process(arr, l, k - 1, dp) + process(arr, k + 1, r, dp));
    }
    // 加上当前区间的长度,并将结果缓存到 DP 数组中
    ans += arr[r + 1] - arr[l - 1];
    dp[l][r] = ans;
    // 返回最终结果
    ans
}

fn main() {
    let n = 7;
    let cuts = [1, 3, 4, 5];
    let cost = min_cost(n, &cuts);
    println!("{}", cost); // 输出:16
}

在这里插入图片描述

本作品采用《CC 协议》,转载必须注明作者和本文链接
微信公众号:福大大架构师每日一题。最新面试题,涉及golang,rust,mysql,redis,云原生,算法,分布式,网络,操作系统。
讨论数量: 1

输入:n = 9, cuts = [5,6,1,4,2]。

题目不是太理解。

4+5 已经等于木棍长度(9)了, 其他的数字都不能在切割了, 这个是什么情况? cuts 数组可以有不用的?

1年前 评论

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!
未填写
文章
464
粉丝
21
喜欢
37
收藏
22
排名:461
访问:1.9 万
私信
所有博文
社区赞助商