动态规划求解硬币兑换算法原理

硬币兑换问题是一个经典的动态规划问题。给定一些不同面额的硬币和一个总金额，编写一个函数来计算可以凑出总金额的硬币组合数。假设每一种面额的硬币数量是无限的。

其核心思想是：使用较小面值的硬币去组合成较大面值的硬币，最终得到总金额。

具体的解题步骤如下：

1. 定义状态：dp[i] 表示组成金额 i 的硬币组合数。

2. 定义状态转移方程：对于每个硬币面额 j，若 j<=i，则 dp[i] += dp[i-j]。

3. 定义初始状态：dp[0] = 1，因为凑出 0 元的钱只有一种方法，那就是不选硬币。

4. 最终答案：dp[amount]。

例如，假设硬币面额为 [1, 2, 5]，总金额为 11，那么可以用以下的方法来解题：

1. 定义状态：dp[i] 表示组成金额 i 的硬币组合数。

2. 定义状态转移方程：dp[i] = dp[i] + dp[i - j]（其中 j 为硬币面额，且 j <= i）。

3. 定义初始状态：dp[0] = 1。

4. 最终答案：dp[11]。

具体的计算过程可以参考以下表格：

| i\j | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| dp[i] | 1 | 1 | 1+1=2 | 1+1+1=3 | 1+1+1+1+1=5 | 1+1+2=4 | 1+1+2+1=5 | 1+1+2+1+1=6 | 1+1+2+2=6 | 1+1+2+2+1=7 | 1+1+2+2+1+1=8 |

因此，硬币面额为 [1, 2, 5]，总金额为 11 的硬币组合数为 8 种。