recursion - 最小硬币变化

问题描述

我是一年级计算机科学专业的学生，目前正在学习递归。我尝试了 Leetcode 322. Coin Change 递归方法，但做不到。但是，我找到了一种解决方案，但在尝试浏览代码后仍然无法理解包括时间和空间复杂性在内的代码。我在下面写了我的问题。（我知道我的问题应该简洁）。非常感谢！

我知道在编写递归时需要遵守三个规则。

定义基本情况：为了使递归函数达到并避免内存堆栈溢出错误）
递归关系：在我写的算法中，我需要改变递归函数的状态，并且需要确保它向基本情况移动
递归调用自身。

Java 代码

public int coinChange(int[] coins, int amount) {
        // Base case 
        if(amount==0) return 0;

        // Question 1 
        int n = amount+1;
        for(int coin : coins) {
            // Question 2
            int current = 0;
            if (amount >= coin) {
                int next = coinChange(coins, amount-coin);
                if(next >= 0)
                    current = 1+next;
            }
            if(current > 0)
                n = Math.min(n,current);
        }
        int finalCount = (n==amount+1) ? -1 : n;
        return finalCount;
    }

1、问题一： int n = amount+1；添加 1 是因为这是归纳步骤吗？我刚刚完成了离散数学科目。这个数量 + 1 让我想起了数学归纳法：基本和归纳步骤。

基本步骤：P(1)
归纳步骤：如果 P(n) 为真，则 P(n+1) 为真。

2.问题2： int current被初始化为0。是为了摆脱排列并确保我得到的硬币组合是唯一的。例如，硬币 = [ 1, 2, 5]，金额 = 11，排列

选项 1 [ 1、2、2、2、2]
选项 2 [ 2, 1, 2, 2, 2]
选项 3 [ 2, 2, 2, 1, 2] 等

3.问题3：当我画递归树时，我可以看到coinChain数字是如何计算的。但我不明白if(next >= 0) curr = 1+next;为什么需要添加 1？coinChange（硬币，金额 -1）。

硬币 = [ 1, 2, 5]，金额 = 11


                                   11 (amount)
                             1/    2|     \5  (coin)
                             10     9      6
                         1/  2| \5
                        9    8   5
                   1/  2| \5
                   8   7    4
                1/ 2| \5
               7   6  3
           1/  2| \5
           6    5  2
       1/  2| \5
      5     4  1
    1/ 2| \5
   4   3   0
1/ 2| \5
etc. until I get to 0.

4. 问题4： int finalCount = (n==amount+1) ? -1 : n;与其这样，不如写成下面这样来提高可读性？还有，为什么当 n == amount +1 时我需要返回 -1？我怎么都想不出来？？？

if(n == amount + 1)
  return -1
else 
  return n;

5. 问题5：时间复杂度是O（硬币数量*数量-伪多项式）还是O（硬币数量^数量）？

6. 问题6：空间复杂度是O(n)吗？每个函数调用都会存储在堆栈内存中，一旦从基本情况返回，就会逐步弹回。

首先十分感谢。

我已经阅读了一些在线帖子，包括以下参考资料。

参考

标签： recursionpermutationcoin-change

recursion - 最小硬币变化 - 递归

问题描述

解决方案

推荐阅读