ความยากขั้นต่ำของตารางงานใน C++

คำอธิบายโจทย์

จัดตารางงาน n งานใน d วัน งาน i ต้องทำหลังงาน j (j

ตัวอย่าง

taskDifficulty = [6,5,4,3,2,1], d = 2 → Output: 7

วันที่ 1: งาน 0-4 (ยาก 6), วันที่ 2: งาน 5 (ยาก 1) รวม = 7

วิธีแก้ปัญหา

ใช้ DP แบบ Top-down + Memoization:

• solve(idx, k): ความยากน้อยที่สุดทำงาน idx...n-1 ใน k วัน
• Base: idx==n && k==0 → 0, k<0 หรือ idx==n && k>0 → INF
• Transition: ลองจบวันนี้ที่ i (idx≤i
• Time: O(n²×d), Space: O(n×d)

การทำงานของโค้ด

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int solve(vector<int>& v, int idx, int k, vector<vector<int>>& dp) {
        if(idx == v.size() && k == 0) return 0;
        if(k < 0 || (idx == v.size() && k > 0)) return 1e6;
        if(dp[idx][k] != -1) return dp[idx][k];
        
        int maxVal = 0, ret = INT_MAX;
        for(int i=idx; i n) return -1;
        vector<vector<int>> dp(n, vector<int>(d+1, -1));
        return solve(j, 0, d, dp);
    }
};

int main() {
    Solution ob;
    vector<int> v = {6,5,4,3,2,1};
    cout << ob.minDifficulty(v, 2);
    return 0;
}

อินพุต

{6,5,4,3,2,1}, 2

เอาต์พุต

7