与递归基本情况作斗争

Question

我花了一段时间研究以下算法：

你会得到不同面额的硬币和总金额。写一个函数来计算你需要的最少数量的硬币来组成这个数量。如果这些硬币的任何组合都不能弥补这个金额，返回-1。

例1：币=[1,2,5]，金额=113 (11 = 5 5 1)

例2：硬币=[2]，金额=3返回-1。

注意：你可以假设每种硬币的数量是无限的。

这可能不是解决问题的最有效方法，但我想我可以通过尝试每一个硬币并每次尝试启动一个新函数来解决它，其中新函数调用具有更新的数量。这将为每枚硬币启动N个函数调用。。。但我稍后会处理这个问题。

现在我正在处理以下问题：通常在进行递归调用时，我无法在基本情况下正确地编写代码。例如，在这个问题中，如果货币的数量不能由硬币的任何组合来弥补，我们必须返回-1。但是，我还需要计算最少的硬币数量。所以我想我应该取一个min变量，然后调用一个新的函数调用。

但是，当这个新的_func_调用最终不起作用时，它会向上传递一个-1到递归调用堆栈，而递归调用堆栈的最小值为零。我不知道该如何调整——我尝试过用不同的方式改变代码，但可能我有一个概念上的问题。我知道为什么会这样，只是不知道怎么处理。

Sample input:
Coins: [2]
Amount: 3

My output: 0
Correct output: -1 

代码：

def coin_change(coins, amount)
    coin_count(coins, amount, coins.min)
end

def coin_count(coins, amount, min_coin)
    with_coin = min = 1.0/0
    return 0 if amount == 0
    return -1 if amount < min_coin
    i = 0

    while i < coins.length
        with_coin = 1 + coin_count(coins, amount - coins[i], min) if amount - coins[i] >= 0
        min = [min, with_coin].min
        i += 1
    end

    min
end

Answer 1

这个问题已经有了一个非常好的答案，它向你展示了如何准确地解决你的问题，但是我想指出你的算法实际上发生了什么，这样你就知道为什么它不适合你。

你的第一个问题是

coin_count(coins, amount - coins[i], min)

应该是

coin_count(coins, amount - coins[i], coins.min)

你不是传递最小的硬币，而是传递你的最小值，你已经设置为无穷大，这使得这个声明检查金额是否小于最小的硬币：

return -1 if amount < min_coin

实际上，检查金额是否小于无穷大，这意味着您的硬币计数总是返回-1。这导致了第二个问题：

1 + coin_count(coins, amount - coins[i], min)
#1 + -1 = 0

在递归编程中使用-1作为错误，令人沮丧的是-1是一个在其他方面有效的数字，并且经常导致逻辑问题。我会避免完全使用它，但如果您的提示或规范强制您返回它，我只会在最后一秒使用它。尝试：

def coin_change(coins, amount)
    result = coin_count(coins, amount, coins.min)
    return -1 if result == 1/0.0
    return result
end

def coin_count(coins, amount, min_coin)
    with_coin = min = 1.0/0
    return 0 if amount == 0
    return 1/0.0 if amount < min_coin
    i = 0

    while i < coins.length
        with_coin = 1 + coin_count(coins, amount - coins[i], coins.min) if amount - coins[i] >= 0
        min = [min, with_coin].min
        i += 1
    end

    min
end

我将您的错误号从-1改为无穷大，这本质上使您的算法忽略了无效排列，因为它们总是由您的用户进行排序。min（）。在这种情况下，函数返回无穷大的唯一方法是它是返回的最小数，这仅在没有有效置换时发生。然后在最少的硬币中，我将其设置为检查无穷大，并返回-1。

哦，顺便说一句，在ruby中有一种更简单的循环方式：

coins.each do |coin|
  with_coin = 1 + coin_count(coins, amount - coin, coins.min) if amount - coin >= 0
  min = [min, with_coin].min
end

Answer 2

你可以这样做。

def count_ways(cents, coins)
  if coins.size == 1
    return (cents % coins.first) == 0 ? [cents/coins.first] : nil
  end 
  coin, *remaining_coins = coins
  (0..cents/coin).each_with_object([]) { |n, arr|
    count_ways(cents-n*coin, remaining_coins).each { |a| arr << [n, *a] } }
end 

def fewest(cents, coins)
  count_ways(cents, coins)&.map(&:sum)&.min
end

fewest(11, [5,2,1])
  #=> 3
fewest(199, [25,10,5,1])
  #=> 13 (Let me guess: 7 quarters, 2 dimes, 4 pennies) 
fewest(2, [3]) 
  #=> nil

require 'time'

t = Time.now
fewest(2835, [25,10,5,1])
  #=> 114 
Time.now - t
  #=> 7.6961 (seconds)

我从我的答案中count_ways。

两个

Answer 3

现在我正在处理以下问题：通常在进行递归调用时，我无法在基本情况下正确地编写代码。例如，在这个问题中，如果货币的数量不能由硬币的任何组合来弥补，我们必须返回-1。但是，我还需要计算最少的硬币数量。

你这里有两个基本情况

1. 如果amount状态变量为零，则我们已完成计数，因此返回count

否则我们有两个递归案例

1. 哎呀：amount小于0，意味着减去的最后一枚硬币（x）太大了-不使用此硬币倒带并递归

这个工作的唯一要求是硬币首先按降序排序

好的，所有这些都很容易用Ruby编码，使用辅助助手（aux）保存状态变量。请记住使用0的计数进行初始化，并确保xs按降序排序。-注意排序只发生一次，而不是每次递归一次

def fewest_coins amount, xs
  def aux count, amount, (x,*xs)
    if amount.zero?
      count
    elsif x.nil?
      -1
    elsif amount < 0
      aux (count - 1), (amount + x), xs
    else
      aux (count + 1), (amount - x), [x, *xs]
    end
  end
  aux 0, amount, xs.sort { |a,b| b <=> a }
end

fewest_coins 11, [1, 5, 2]         # => 3
fewest_coins 2, [3]                # => -1
fewest_coins 100, [1, 25, 10, 5]   # => 4

检查你的理解

作为练习，修改最少的_硬币以输出组成答案的硬币数组

# for example
fewest_coins 199, [1, 5, 10, 25, 50]
# => [50, 50, 50, 25, 10, 10, 1, 1, 1, 1]