Chương trình tìm tổng độ khó nhỏ nhất hoàn thành công việc trong k ngày C++

Mô tả bài toán

Cho mảng jobs (độ khó) và số k. Phải làm theo thứ tự, mỗi ngày làm ít nhất một việc. Độ khó một ngày = max độ khó các việc ngày đó. Tìm tổng độ khó nhỏ nhất trong k ngày.

Ví dụ: jobs = [2,3,4,6,3], k=2 → 8 (ngày 1: [2], ngày 2: [3,4,6,3] → 2+6=8).

Giải thuật (DP đệ quy có nhớ)

1. dp[start][k] = tổng độ khó nhỏ nhất từ start với k ngày còn lại.
2. DFS(start, k):
   • Nếu start >= n: return k==0 ? 0 : INF.
   • Nếu k < 0: return INF.
   • Duyệt i từ start đến n-1: maxVal = max(maxVal, jobs[i]); ret = min(ret, maxVal + dfs(i+1, k-1)).
   • Lưu dp[start][k] = ret.

Ví dụ minh họa (C++)

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

const int INF = 1e6;
int dp[505][15];

int dfs(int start, int k, vector<int>& v) {
    if (start >= v.size()) return k == 0 ? 0 : INF;
    if (k < 0) return INF;
    if (dp[start][k] != -1) return dp[start][k];
    int ret = INF, val = 0;
    for (int i = start; i < v.size(); i++) {
        val = max(val, v[i]);
        ret = min(ret, val + dfs(i+1, k-1, v));
    }
    return dp[start][k] = ret;
}

int solve(vector<int>& jobs, int k) {
    memset(dp, -1, sizeof dp);
    return dfs(0, k, jobs);
}

int main() {
    vector<int> v = {2,3,4,6,3};
    int k = 2;
    cout << solve(v, k);
    return 0;
}

Đầu vào

{2,3,4,6,3}, 2

Đầu ra

8