1335.工作计划的最低难度

链接：1335.工作计划的最低难度
难度：Hard
标签：数组、动态规划
简介：返回整个工作计划的 最小难度 。如果无法制定工作计划，则返回 -1 。

题解 1 - cpp

• 编辑时间：2023-05-16
• 执行用时：52ms
• 内存消耗：7.4MB
• 编程语言：cpp
• 解法介绍：dp[i][j]表示只有i天时，只有j个job时的最小难度。

class Solution {
public:
    int minDifficulty(vector<int>& jobDifficulty, int d) {
        int n = jobDifficulty.size(), num = 0;
        if (n < d) return -1;
        vector<vector<int>> dp(d, vector<int>(n, INT_MAX));
        for (int i = 0; i < n; i++) dp[0][i] = num = max(num, jobDifficulty[i]);
        for (int dd = 1; dd < d; dd++) {
            for (int i = dd; i < n; i++) {
                num = 0;
                for (int j = i; j >= dd; j--) {
                    num = max(num, jobDifficulty[j]);
                    dp[dd][i] = min(dp[dd][i], dp[dd - 1][j - 1] + num);
                }
            }
        }
        return dp[d - 1][n - 1];
    }
};

题解 2 - python

• 编辑时间：2023-05-16
• 执行用时：892ms
• 内存消耗：16.2MB
• 编程语言：python
• 解法介绍：同上。

class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        n = len(jobDifficulty)
        if n < d:
            return -1
        num = 0
        dp = [[inf for _ in range(n)] for _ in range(d)]
        for i in range(n):
            dp[0][i] = num = max(num, jobDifficulty[i])
        for dd in range(1, d):
            for i in range(dd, n):
                num = 0
                for j in range(i, dd - 1, -1):
                    num = max(num, jobDifficulty[j])
                    dp[dd][i] = min(dp[dd][i], dp[dd - 1][j - 1] + num)
        return dp[d - 1][n - 1]

题解 3 - rust

• 编辑时间：2023-05-16
• 执行用时：4ms
• 内存消耗：2.1MB
• 编程语言：rust
• 解法介绍：同上。

impl Solution {
    pub fn min_difficulty(job_difficulty: Vec<i32>, d: i32) -> i32 {
        let d = d as usize;
        let n = job_difficulty.len();
        if n < d {
            -1
        } else {
            let mut num = 0;
            let mut dp = vec![vec![i32::MAX; n]; d];
            for i in 0..n {
                num = num.max(job_difficulty[i]);
                dp[0][i] = num;
            }
            for dd in 1..d {
                for i in dd..n {
                    num = 0;
                    for j in (dd..=i).rev() {
                        num = num.max(job_difficulty[j]);
                        dp[dd][i] = dp[dd][i].min(dp[dd - 1][j - 1] + num);
                    }
                }
            }
            dp[d - 1][n - 1]
        }
    }
}