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

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)）。正确答案是什么？

我似乎对递归函数内部的循环很费劲，有时我们似乎在时间复杂度中计算它们，而其他时候它们已经 "priced in" 在我怀疑的子问题中这里的案例。

Answer 1

正如 Enrico Borba 评论的那样：

我觉得你的分析是正确的。您的 table 中有 O(amount * number of coins) 个单元格，要计算 table 中的任何单元格，您运行循环（硬币数）次。您编写的代码具有这种复杂性。很可能存在具有 O(数量 * 硬币数量) 复杂度的不同算法。

– 恩里科·博尔巴

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

What is the time complexity of this coin change algorithm?

algorithm

recursion

time-complexity

memoization

coin-change