题目描述：

输入一个含有不同面额的整数数组 和 一个目标金额，计算有多少种方法能够使用给出的面额达成目标金额。每个面额的使用使用数量不限

举个栗子：

目标金额是10，当前面值的数组是 [1, 5, 10, 25 ]

总共是4种方法达到这个数额，分别是

① 1 * 10     ② 2 * 5   ③ 1* 5 + 5 * 1 ④ 10 * 1

解题思路：

我们需要先创建一个数组，名字叫它ways

ways一开始是等于 [ 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ] 长度是面值 +1。索引对应的是面值，0号索引对应的面值是1。ways中的每个数值代表的是当前输入的面额达到目标金额的总共的方法。初始化时候第一个数组中的第一个值一定要是1。

为了计算这题我们有一个公式：ways[ 目标金额 ] += ways[ 目标金额 - 面值 ] 

这个公式使用的情况是在目标金额大于面值的情况下。思考一下，如果你手中有一张面额10元，你永远无法将它凑成五元，在这个题目里。所以我们要做的是先判断目标金额是否大于面值。

根据这个公式我们先写出我们的伪代码（字丑轻喷）

遍历在面额数组中的数字，然后遍历ways数组中的数字，里面的数字是记录当前面额可以达到面额的方式有多少种。

每遍历ways中个一个元素我们就要记得比对一下目标金额是否大于金额（ 记住目标金额就是下标！）。判断完之后我们就可以使用公式了。

伪代码

这是初始化的数组

初始化数组

当面额为1的时候，ways[1] = ways[1] + ways[1 - 1]

ways[1] = 0, ways[ 1 - 1] = 1，所以相加之后等于1，后面以此类推

（图中少写了个s抱歉）

面额为1的时候

后面也以此类推，自己推时候请注意面额为5的时候， 面额为10的方法是3，因为 ways[10] = 1 , ways[10 - 5] = 2，因为面额为5的时候更新过一次。最终我们可以得到面额为10的时候有4中方法可以达到。

所有过程

空间复杂度和时间复杂度

空间复杂度是O(n)，这里的n是指的目标金额，因为我们需要创建一个 目标金额 + 1 大小的数组去计算

时间复杂度是O(n*d)，n代表的是目标金额，d代表的是现有的面额，在伪代码里面我们可以看到我们需要两个循环来遍历我们的数组，第一个是遍历n第二个是遍历d，所以最终的时间复杂度是O(n*d)

代码：

Reference：代码来自Algoexpert，以学习作为主要目的来分享的。