在硬币兑换类型的问题中将递归函数重构为迭代函数

Question

在coin-change类型的问题中，我试图将递归函数重构为迭代函数。给定一组coin_types，函数coinr递归地查找要支付给定金额sum的最小硬币数量。

# Any coin_type could be used more than once or it may not be used at all

sub coinr ($sum, @coin_types) { # As this is for learning basic programming 
    my $result = $sum;          # No memoization (dynamic programming) is used
    if $sum == @coin_types.any { return 1 }
    else { for @coin_types.grep(* <= $sum) -> $coin_type {
        my $current = 1 + coinr($sum - $coin_type, @coin_types);
        $result = $current if $current < $result; } }
    $result;
}

say &coinr(@*ARGS[0], split(' ', @*ARGS[1])); 

# calling with
# 8 "1 4 5" gives 2 (4+4)
# 14 "1 3 5" gives 4 (1+3+5+5), etc.

这个函数最初是用Python编写的，我把它转换成了Raku。以下是我对迭代版本的看法，它非常不完整：

# Iterative

sub coini ($sum, @coin_types) {
    my $result = 1;
    for @coin_types -> $coin_type {
    for 1 ... $sum -> $i {
        if $sum-$coin_type == @coin_types.any { $result += 1 } #?
        else { # ???
        }
     }
   }
}

有人能帮帮我吗？

Answer 1

有许多不同的方法可以迭代地实现这一点(正如我们所说的，有不止一种方法可以做到这一点！)这里有一种方法：

sub coini($sum is copy, @coin-types) {
    gather while $sum > 0 { take $sum -= @coin-types.grep(* ≤ $sum).max } .elems
}

这会尽可能地减少(现在可变的) $sum，并在列表中跟踪当前的$sum。然后，因为我们只需要硬币的数量，所以它返回该列表的长度。