硬币找零DP解法 - 迭代循环的顺序为什么很重要

Question

为什么迭代循环的顺序在这里很重要？

    def change1(self, amount, coins):
        """
        :type amount: int
        :type coins: List[int]
        :rtype: int
        """
        if amount == 0:
            return 1

        dp = [0 for _ in range(amount + 1)]
        dp[0] = 1

        # dp[i] to denote the number of ways to sum up to amount i.
        for j in range(len(coins)): # switch those 2 statements would be wrong answer why???
            for i in range(1, amount + 1):
                if i - coins[j] >= 0:
                    dp[i] += dp[i - coins[j]]

        return dp[amount]

    def change2(amount, coins): # wrong answer
        """
        :type amount: int
        :type coins: List[int]
        :rtype: int
        """
        if amount == 0:
            return 1

        dp = [0 for _ in range(amount + 1)]

        ## when amount is 0, # combinations is 1
        dp[0] = 1

        # dp[i] to denote the number of ways to sum up to amount i.
        for i in range(1, amount + 1):
            for j in range(len(coins)):  # switch those 2 statements would be wrong answer why???
                if i - coins[j] >= 0:
                    dp[i] += dp[i - coins[j]]

        return dp[amount]

变更 1

dp[i-1] = dp[i-1-c2] + dp[i-1-c2] + dp[i-2-c2] + ..dp[0]

dp[i] = dp[i-c1] + dp[i-1-c1] + dp[i-2-c1] + ...dp[0] 这是正确的解决方案。

变更 2

dp[i-1] = dp[i-1-c1] + dp[i-1-c2] + dp[i-1-c3] + dp[i-1-c4] + ... dp[0]

dp[i] = dp[i-c1] + dp[i-c2] + dp[i-c3] + dp[i-c4] + ... dp[0]

为什么这个方法是错误的？

总量i可以从取硬币c1或c2或c3的选择之和中导出，这在我看来更加直观。

我已经查了一些参考资料，但没有找到令人满意的答案。

编辑：我也理解改变嵌套循环的顺序会得到错误的答案，我正在努力理解为什么第二种方法有错误的直觉而第一种方法是正确的。

硬币找零问题：考虑顺序和不考虑顺序时的解法数量

使用动态规划的硬币找零问题

- jen007

Answer 1

当您更改嵌套循环的顺序时，显然会得到错误的答案。

该问题的正确dp状态定义如下：

dp[i][j] = # of ways to form amount j using first i coins

这里的最优子结构是，一旦你有了前i个硬币的解决方案，就可以将其扩展到i+1个硬币。

但是，当你颠倒循环执行顺序时，这种子结构属性就不再成立。

在这种情况下，你首先计算使用所有硬币形成金额i的方法数量，并将其扩展以找到形成金额i+1的方法数量，而这种最优子结构属性并不成立。

- Raj

---

我没有使用 dp[i][j]，而是用 dp[amount] 表示总和为 i 的方法数。根据定义，它应该是 dp[amount] = dp[amount-c1] + dp[amount-c2] ...。 - undefined

为了简单解释，我使用了dp[i][j]。如果你仔细观察，你会发现在dp[n][amount]上定义的dp状态等同于dp[amount]，在每次迭代中，不是更新原始的dp数组，而是为每次迭代创建一个新的行。 - undefined

是的，如果您从 dp[i][j] 进行优化，上述解释是有道理的，然而，使用 dp[amount] 表示方法总数也没有问题，它表示使用任何硬币凑出总金额的方法数。 - undefined

两者都是一样的！https://dev59.com/XF4c5IYBdhLWcg3weaT8 - undefined

谢谢，基本上，在我的情况下，dp[amount]的含义是错误的，dp[amount]实际上是用前j个硬币组成金额i的方法数。 - undefined