반응형
https://leetcode.com/problems/minimum-difficulty-of-a-job-schedule
Minimum Difficulty of a Job Schedule - LeetCode
Can you solve this real interview question? Minimum Difficulty of a Job Schedule - You want to schedule a list of jobs in d days. Jobs are dependent (i.e To work on the ith job, you have to finish all the jobs j where 0 <= j < i). You have to finish at lea
leetcode.com
class Solution {
public:
int dp[300][11];
int minDifficulty(vector<int>& jobDifficulty, int d) {
for(int i=0; i<jobDifficulty.size(); i++)
for(int j=1; j<=d; j++) dp[i][j] = INT_MAX;
int res = minDifficulty(jobDifficulty, 0, d);
return res != INT_MAX ? res : -1;
}
int minDifficulty(vector<int>& jobDifficulty, int idx, int d) {
if(idx == jobDifficulty.size() && d == 0) {
return 0;
}
if(idx == jobDifficulty.size() || d == 0) {
return INT_MAX;
}
if(dp[idx][d] != INT_MAX) return dp[idx][d];
int mx = 0;
for(int i=idx; i<jobDifficulty.size(); i++) {
mx = max(mx, jobDifficulty[i]);
int res = minDifficulty(jobDifficulty, i + 1, d - 1);
if(res != INT_MAX) {
dp[idx][d] = min(dp[idx][d], mx + res);
}
}
return dp[idx][d];
}
};
반응형
'Algorithm' 카테고리의 다른 글
| LeetCode 1624. Largest Substring Between Two Equal Characters (1) | 2023.12.31 |
|---|---|
| LeetCode 1897. Redistribute Characters to Make All Strings Equal (0) | 2023.12.30 |
| LeetCode 1155. Number of Dice Rolls With Target Sum (0) | 2023.12.27 |
| LeetCode 91. Decode Ways (0) | 2023.12.25 |
| LeetCode 1758. Minimum Changes To Make Alternating Binary String (0) | 2023.12.25 |