Отношение повторения динамического программирования

Question

Я пытаюсь найти и решить соотношение рекуррентности для подхода с динамическим программированием до UVA #11450. Как отказ от ответственности, это часть домашнего задания, которое я в основном закончил, но смущен насчет анализа.

Вот мой (рабочий) Код:

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]; 
} 

У меня возникли проблемы с несколькими аспектами анализа:

• Что является основной операцией? Моя первоначальная реакция была бы вычитанием, так как каждый раз, когда мы вызываем функцию, мы вычитаем ее из C.
• Поскольку рекурсивный вызов находится внутри цикла, означает ли это просто умножение в рекуррентном отношении?
• Как я могу объяснить, что он использует динамическую таблицу в отношении повторения? Я знаю, что некоторые проблемы разлагаются на линейные, когда используется табула, но я не уверен, как это разлагается.

Я знаю, что сложность (по Algorithmist) является O (M * C * макс (K)), где К число моделей каждого предмета одежды, но я изо всех сил, чтобы работать в обратном направлении, чтобы получить повторение отношение. Вот мое предположение:

S (с) = к * S (с-1) + 1, S (0) = 0

Однако это не принимает во внимание M.

Мысли?

Answer 1

Вы можете думать о каждом состоянии DP (m,c) как вершина графа, где рекурсивные вызовы штатов (m-item_i,c-1) являются краями от (m,c) до (m-item_i,i).

Запоминание вашей рекурсии означает, что вы только начинаете поиск с вершины один раз, а также обрабатываете его исходящие края только один раз. Итак, ваш алгоритм по существу является линейным поиском на этом графике и имеет сложность O(|V|+|E|). Существуют вершины M * C и не более max(K) края, выходящие из каждого, поэтому вы можете связать количество ребер на O(M*C*max(K)).