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

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在列表中跟踪当前。然后，由于我们只想要硬币的数量，它返回该列表的长度。