# How should I apply dynamic programming on the following problem

I have an array of events where `events[i] = [startDay_i, endDay_i, value_i]`. The `ith` event starts at `startDay_i` and ends at `endDay_i`, Attending the `ith` event, I will receive `value_i`. Also given an integer `k` which represents the maximum number of events I can attend.

It's required to attend the event only once at a time, and not allowed to attend two events with overlapping time.

I want to calculate the maximum sum of values by attending events.

I tried to use dynamic programming to solve this: let `f[i]` be the maximum sum within `i` days, and it depends on every `f[j]` where `j < i`, and I have to iterate every `j` and find out the events that endDay is before `i`. This is a O(n^3) approach. Any way I can do it better?

This is a O(n^3) approach

The time complexity has to do with `k` as well. The DP should give you a O(nk) instead.

Similar with a knapsack problem, you can use a recursive way with memorization to implement the DP.

• Sort the event by `startDay` (by `endDay` if `startDay` equals).
• Memorize the maximum value you can get by attending `x` events prior to time `t`.
• For each depth of recursion, you can either attend the current event or skip, so the recursive logic looks like
``````int solve(int x, int t, int count)
{
// some edge cases processing

if (cache has the value for x and t)
{
return cache.get(x, t);
}

// skip current event
int max = solve(x+1, t, count);
if (events[cur][0] > t) // make sure no overlapping on the events
{
max = max(max, solve(x+1, events[x][1], count+1) + events[x][2]);
}

// Add max value to the cache with x, t as its key

return max;
}
``````