可能重复:
递归进行更改:如何修改我的算法以打印所有组合?
在硬币图案计数问题中(给定一个值 N 和一组固定的硬币,我们必须计算加起来为 N 的硬币组合的数量。),如果我们想打印组合而不是计算组合,什么是该方法 ?我必须为此使用动态编程吗?
可能重复:
递归进行更改:如何修改我的算法以打印所有组合?
在硬币图案计数问题中(给定一个值 N 和一组固定的硬币,我们必须计算加起来为 N 的硬币组合的数量。),如果我们想打印组合而不是计算组合,什么是该方法 ?我必须为此使用动态编程吗?
是的,你需要它。假设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]
)。