# Activity Selection in Dynamic Programming

I'm trying to write pseudocode for the Activity Selection Problem in dynamic programming as opposed to Greedy Algorithm. The recurrence I have is:

c[i,j] = max(c[i,k] + c[k,j] + 1), where c[i,j] denotes the size of an optimal solution for set of activities.

So far, I have:

ACTIVITY-DYNAMIC(s, f)
n = length(s)
c = []
for i to n
c[i] = max(c[i,k] + c[k,j] + 1)


But I can't seem to figure out what to do next. Any suggestions, pointers?

-
You should start the function by initializing the end-cases (i.e. $c[0,i]$ and $c[i,0]$ for all $i$). Then, fill the array according to the recurrence relation. Note that filling the array requires a 2-dimensional loop (traversing $i,j$), and within this loop, use an inner loop to take the maximum over $k$. –  Shaull Feb 19 at 15:11
How would I pick k in this case? Also, would I fill c[0,i] and c[i,0] with zeros? –  Darksky Feb 19 at 15:18
Sorry, I was thinking of something different in the previous comment. I'm not sure it's relevant here. Could you clarify how you ended up with this recurrence relation, and what exactly $c[i,j]$ denotes? –  Shaull Feb 19 at 15:26
Well its the typical activity selection recurrence which I've been reading about. It's quite long to explain in a comment, but its the standard one. Here's a link that explains it: sanlp.org/daa/slides/… –  Darksky Feb 19 at 15:49
Ok, so what I wrote above wasn't far off. You start by initializing the base conditions: all the cases where you already know the value of $c[i,j]$, which is exactly those where $S_{ij}=\emptyset$. These are exactly $S_{ij}$ such that $i\ge j$ (so everything below the diagonal). Now that this is filled, you can proceed with the triple loop mentioned above to fill the rest of the table bottom-up. Finally, you return $c[0,n]$. –  Shaull Feb 19 at 15:59
add comment