Dynamic programming recurrence relation

Question

I am trying to find and solve the recurrence relation for a dynamic programming approach to UVA #11450. As a disclaimer, this is part of a homework assignment that I have mostly finished but am confused about the analysis.

Here is my (working) code:

int shop(int m, int c, int items[][21], int sol[][20]) {
    if (m < 0) return NONE;                  // No money left
    if (c == 0) return 0;                    // No garments left
    if (sol[m][c] != NONE) return sol[m][c]; // We've been here before

    // For each model of the current garment
    for (int i = 1; i <= items[c-1][0]; i++) {
        // Save the result
        int result = shop(m-items[c-1][i], c-1, items, sol);

        // If there was a valid result, record it for next time
        if (result != NONE) sol[m][c] = max(sol[m][c], result+items[c-1][i]);
    }

    return sol[m][c];
}

I am having trouble with a few aspects of the analysis:

• What is the basic operation? My initial reaction would be subtraction, since each time we call the function we subtract one from C.
• Since the recursive call is within a loop, does that just mean multiplication in the recurrence relation?
• How do I factor in the fact that it uses a dynamic table into the recurrence relation? I know that some problems decompose into linear when a tabula is used, but I'm not sure how this one decomposes.

I know that the complexity (according to Algorithmist) is O(M*C*max(K)) where K is the number of models of each garment, but I'm struggling to work backwards to get the recurrence relation. Here's my guess:

S(c) = k * S(c-1) + 1, S(0) = 0

However, this fails to take M into account.

Thoughts?

Answer 1

You can think of each DP state (m,c) as a vertex of a graph, where the recursive calls to states (m-item_i,c-1) are edges from (m,c) to (m-item_i,i).

Memorization of your recursion means that you only start the search from a vertex once, and also process its outgoing edges only once. So, your algorithm is essentially a linear search on this graph, and has complexity O(|V|+|E|). There are M*C vertices and at most max(K) edges going out of each one, so you can bound the number of edges by O(M*C*max(K)).