工作計劃的最低難度【LC1335】

你需要制定一份 d 天的工作計劃表。工作之間存在依賴，要想執(zhí)行第 i 項工作，你必須完成全部 j 項工作（ 0 <= j < i）。

你每天 至少 需要完成一項任務(wù)。工作計劃的總難度是這 d 天每一天的難度之和，而一天的工作難度是當(dāng)天應(yīng)該完成工作的最大難度。

給你一個整數(shù)數(shù)組 jobDifficulty 和一個整數(shù) d，分別代表工作難度和需要計劃的天數(shù)。第 i 項工作的難度是 jobDifficulty[i]。

返回整個工作計劃的 最小難度 。如果無法制定工作計劃，則返回 -1 。

我和動態(tài)規(guī)劃的關(guān)系就像是見過但是總是隱隱約約想不起來的陌生人
類似題目

dfs+記憶化

• 思路

  題意可以轉(zhuǎn)化為分割成d個子數(shù)組，使d個子數(shù)組的最大值之和最小。

  • 尋找子問題：如果將后$[k,n?1]$個任務(wù)在一天內(nèi)完成，那么前面$[0,k?1]$個任務(wù)需要在$d?1$天完成，因此找到了子問題，可以通過遞歸/動態(tài)規(guī)劃來解決。（dfs+記憶化的形式最好理解）

  • 定義dfs函數(shù)：定義$dfs(i,j)$為在$i$天完成$[0,j]$個任務(wù)所需要的最小難度

  • 遞歸入口：那么$dfs(n?1,d)$即為答案

  • 遞歸邏輯：

    由于每一天都需要有工作任務(wù)，那么在決定第$i$天的工作任務(wù)時，必須預(yù)留$i?1$個工作。因此在安排第$i$天的工作任務(wù)時，我們枚舉$[i?1,j]$個任務(wù)，分割子數(shù)組，記錄子數(shù)組中的最大值（當(dāng)天的工作難度），然后遞歸到下一天，取最小值返回。
    d f s ( i , j ) = m i n k = i ? 1 j { d f s ( i ? 1 , k ? 1 ) + m a x p = k j ( j o b D i f f i c u l t y [ p ] ) } dfs(i,j)= min_{k= i-1}^{j}\{dfs(i-1,k-1)+max_{p=k}^{j}(jobDifficulty[p])\} dfs(i,j)=mink=i?1j?{dfs(i?1,k?1)+maxp=kj?(jobDifficulty[p])}

  • 遞歸邊界：

    只有一天時，必須完成所有任務(wù)

• 實現(xiàn)

  (i可以整體縮小1)

  class Solution {
      int[] jobDifficulty;
      int[][] memo;
      int res = Integer.MAX_VALUE;
      public int minDifficulty(int[] jobDifficulty, int d) {
          this.jobDifficulty = jobDifficulty;
          // 分割成d個子數(shù)組，使d個子數(shù)組的最大值之和最小
          // dfs(i,j) j天完成[0,i]項工作所需要的最小難度
          int n = jobDifficulty.length;
          if (n < d){
              return -1;
          }
          memo = new int[d + 1][n];
          for (int i = 0; i <= d; i++){
              Arrays.fill(memo[i], -1);
          }
          return dfs(d, n - 1);
          
      }
      public int dfs(int i, int j){
          // if (i < 0 || j <= 0) return 0;
          if (memo[i][j] != -1) return memo[i][j];
          // 只有一天
          if (i == 1){
              int mx = 0;
              for (int k = 0; k <= j; k++){
                  mx = Math.max(mx, jobDifficulty[k]);
              }
              memo[i][j] = mx;
              return mx;
          }
          int res = Integer.MAX_VALUE;
          int mx = -1;
          // 枚舉子數(shù)組范圍 [i - 1, j] 留下i - 1個元素
          for (int k = j; k >= i - 1; k--){
              mx = Math.max(mx, jobDifficulty[k]);
              res = Math.min(res, mx + dfs(i - 1,k - 1));
          }
          memo[i][j] = res;
          return res;
      }
  }
  

  • 復(fù)雜度

    • 時間復(fù)雜度：$O(n^{2}d)$
    • 空間復(fù)雜度：$O(nd)$

遞推

• 實現(xiàn)

  class Solution {
      public int minDifficulty(int[] a, int d) {
          int n = a.length;
          if (n < d) return -1;
  
          var f = new int[d][n];
          f[0][0] = a[0];
          for (int i = 1; i < n; i++)
              f[0][i] = Math.max(f[0][i - 1], a[i]);
          for (int i = 1; i < d; i++) {
              for (int j = n - 1; j >= i; j--) {
                  f[i][j] = Integer.MAX_VALUE;
                  int mx = 0;
                  for (int k = j; k >= i; k--) {
                      mx = Math.max(mx, a[k]); // 從 a[k] 到 a[j] 的最大值
                      f[i][j] = Math.min(f[i][j], f[i - 1][k - 1] + mx);
                  }
              }
          }
          return f[d - 1][n - 1];
      }
  }
  
  作者：靈茶山艾府
  鏈接：https://leetcode.cn/problems/minimum-difficulty-of-a-job-schedule/solutions/2271631/jiao-ni-yi-bu-bu-si-kao-dong-tai-gui-hua-68nx/
  來源：力扣（LeetCode）
  著作權(quán)歸作者所有。商業(yè)轉(zhuǎn)載請聯(lián)系作者獲得授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。
  

  • 復(fù)雜度文章來源地址http://www.zghlxwxcb.cn/news/detail-447505.html

    • 時間復(fù)雜度：$O(n^{2}d)$
    • 空間復(fù)雜度：$O(nd)$

到了這里，關(guān)于【每日一題Day208】LC1335工作計劃的最低難度 | 動態(tài)規(guī)劃的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！