1

可能重复:
递归进行更改:如何修改我的算法以打印所有组合?

在硬币图案计数问题中(给定一个值 N 和一组固定的硬币,我们必须计算加起来为 N 的硬币组合的数量。),如果我们想打印组合而不是计算组合,什么是该方法 ?我必须为此使用动态编程吗?

4

1 回答 1

2

是的,你需要它。假设dp[i]等于加起来的组合数,i则以下伪代码打印所有组合:

print_combinations(amount_left, current_coin):
    if amount_left == 0:
        print "\n"
        return
    if current_coin == num_coins:
        return
    if dp[amount_left - coins[current_coin]] > 0:
        print coins[current_coin], " "
        print_combinations(amount_left - coins[current_coin], current_coin)
    print_combinations(amount_left, current_coin + 1)

此函数打印coins [current_coin .. last_coin]加起来为 amount_left 的所有组合。所以最初的调用是print_combinations(N, 0),正如你所看到的,动态规划表dp[]帮助我们决定是否使用当前硬币进行递归(我们只有在至少有一个组合加起来等于剩余的新数量时才会递归amount_left - coins[current_coin])。

于 2012-10-10T04:59:36.837 回答