algorithm - 动态规划递推关系

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

我在分析的几个方面遇到了问题:

• 基本操作是什么？我最初的 react 是减法，因为每次我们调用该函数时，我们都会从 C 中减去一个。
• 既然递归调用是在一个循环中，那是否意味着递归关系中的乘法？
• 我如何将它使用动态表这一事实考虑到递归关系中？我知道使用表格时有些问题会分解为线性问题，但我不确定这个问题是如何分解的。

我知道复杂性(根据 Algorithmist )是 O(M*C*max(K)) ，其中 K 是每件衣服的型号数量，但我正在努力向后工作以获得重复关系。这是我的猜测:

S(c) = k * S(c-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)) 限制边的数量。