LeetCode 1335. Minimum Difficulty of a Job Schedule

動的計画法

問題：https://leetcode.com/problems/minimum-difficulty-of-a-job-schedule/

概要：配列aが与えられる. これをd分割したときの区間ごとの最大値の和の最小値を求める

考えたこと：区間分割なので「どこで区切ったか」、「どこまで区切ったのか」という情報を扱いたくなる。今回の場合、これは次のように添え字を持つことで動的計画法で実現できる。

dp[i][j] = i番目まで見て、j個の集合が存在する

次に遷移について考える。

i-1番目までを見たとき, 次の分割の番地はi

int minDifficulty(vector<int>& jobDifficulty, int d) {
   long dp[310][15];
   for(int i=0; i<310; i++){
      for(int k=0; k<15; k++){
         dp[i][k] = INT_MAX;
      }
   }
   dp[0][0] = 0; 
   int n = jobDifficulty.size();
   for(int i=0; i<n; i++){
      for(int j=i; j<n; j++){
         long maxV = 0;
         for(int k=i; k<=j; k++){
            maxV = max(maxV, (long)jobDifficulty[k]);
         }
         for(int k=d; k>0; k--){
            if(dp[i][k-1] == INT_MAX) continue;
            dp[j+1][k] = min(dp[j+1][k], dp[i][k-1] + maxV);
         }
      }
   }
   if(dp[n][d] == INT_MAX) return -1;
   return dp[n][d];
}