动态规划硬币找零算法

动态规划硬币找零算法是一种常见的解决硬币找零问题的方法。该问题是给定一定面额的硬币和一个目标金额，找出最少需要的硬币数量来凑成目标金额。

算法的思路是利用子问题的最优解来计算更大问题的最优解。具体步骤如下：

1. 创建一个大小为目标金额+1的数组dp，并初始化所有元素为正无穷大。
2. 将dp[0]设置为0，表示目标金额为0时需要0个硬币。
3. 对于每个硬币的面额coin，遍历dp数组，更新dp[j]的值，其中j表示当前的目标金额：
- 如果j >= coin，说明当前的目标金额可以由之前的金额加上一个硬币coin得到，此时更新dp[j]为dp[j-coin]+1和dp[j]的较小值。
- 如果j < coin，则无法使用当前硬币coin来凑成目标金额，保持dp[j]不变。
4. 最终，dp[目标金额]即为所需的最少硬币数量。

这种算法的时间复杂度为O(N*M)，其中N为目标金额，M为硬币面额的数量。