该硬币找零算法的时间复杂度是多少？

Question

我在leetcode上解决了硬币兑换问题https://leetcode.com/problems/coin-change-2/。

这是我写的代码：

    def change(self, amount: int, coins: List[int]) -> int:
        def helper(amount, coins, ind):
            if amount == 0:
                return 1
            if amount < 0:
                return 0
            if (amount, ind) in dp:
                return dp[(amount, ind)]

            res = 0
            for i in range(ind, len(coins)):
                res  += helper(amount - coins[i], coins, i)

            dp[(amount, ind)] = res
            return res

        coins.sort()
        dp = {}
        return helper(amount, coins, 0)

我注意到我在分析记忆算法的时间复杂度方面遇到了很多困难。例如，在这种情况下，我认为我们有amount * number of coins子问题 - >因此算法O(amount * number of coins * number of coins)在我的因子中以第二个硬币数量运行来自这样一个事实：对于每个子问题，我们必须通过循环来for i in range(ind, len(coins)):将结果相加。

然而，这个解决方案似乎实际上O(amount * number of coins)来自我读到的内容（并且自下而上的方法是O(amount * number of coins)）。正确答案是什么？

我似乎在递归函数内部的循环上遇到了很多困难，有时我们似乎在时间复杂度中计算它们，而有时它们已经在子问题中“定价”，就像我怀疑的情况一样。

Answer 1

正如恩里科·博尔巴评论道：

\n\n

你的分析对我来说似乎是正确的。您的表中有O(amount * number of coins)单元格，并且要计算表中的任何单元格，您需要运行循环（硬币数量）次。您编写的代码具有这种复杂性。很可能有一种不同的算法，其复杂度为 O（金额 * 硬币数量）。

\n\n

\xe2\x80\x93 恩里科·博尔巴

\n