1335.工作计划的最低难度.md

1335.工作计划的最低难度

/*
 * @lc app=leetcode.cn id=1335 lang=typescript
 *
 * [1335] 工作计划的最低难度
 */

// @lc code=start
function minDifficulty(jobDifficulty: number[], d: number): number {}
// @lc code=end

解法 1: 动态规划

function minDifficulty(jobDifficulty: number[], d: number): number {
  const n = jobDifficulty.length
  const dp = Array.from({ length: n }, () => new Array(d + 1).fill(Infinity))

  for (let i = 0; i < n; i++) {
    for (let j = 1; j <= d; j++) {
      let max = jobDifficulty[i]
      for (let k = i; k >= 0; k--) {
        max = Math.max(max, jobDifficulty[k])
        dp[i][j] = Math.min(dp[i][j], (dp[k - 1]?.[j - 1] ?? Infinity) + max)
      }
      if (j === 1) dp[i][j] = Math.min(dp[i][j], max)
    }
  }

  return dp[n - 1][d] === Infinity ? -1 : dp[n - 1][d]
}

Case

test.each([
  { input: { jobDifficulty: [6, 5, 4, 3, 2, 1], d: 2 }, output: 7 },
  { input: { jobDifficulty: [9, 9, 9], d: 4 }, output: -1 },
  { input: { jobDifficulty: [1, 1, 1], d: 3 }, output: 3 },
])('input: jobDifficulty = $input.jobDifficulty, d = $input.d', ({ input: { jobDifficulty, d }, output }) => {
  expect(minDifficulty(jobDifficulty, d)).toEqual(output)
})