思路：

还是老样子，还是先使用递归方式来解，然后通过递归推动态规划。那递归如何设计?

定义一个递归方法：表示从index开始到N达到剩下的值（目标值减去上一步的值）做少可以得到数量是多少。int process(int[] coins, int index, int rest)。代码如下：

java">public static int coinChange(int[] coins, int amount) {// 如果硬币数组为空或长度为0，则无法进行兑换，返回-1if (coins == null || coins.length == 0) {return -1;}// 调用递归函数计算最少硬币数int result = process(coins, 0, amount);// 如果结果是Integer.MAX_VALUE，说明没有找到有效组合，返回-1return result == Integer.MAX_VALUE ? -1 : result;
}private static int process(int[] coins, int index, int rest) {// 如果剩余金额为0，说明找到了一个有效的硬币组合，返回0（不需要更多硬币）if (rest == 0) {return 0;}// 如果硬币数组已经全部考虑完毕，或者剩余金额小于0，则当前路径不可行，返回Integer.MAX_VALUEif (index == coins.length || rest < 0) {return Integer.MAX_VALUE;}// 当前考虑的硬币int coin = coins[index];// 最多可以使用当前硬币的次数int zhang = rest / coin;// 初始化最小硬币数为最大整数，方便后面取最小值int min = Integer.MAX_VALUE;// 遍历每个可能的硬币数，从0开始到zhangfor (int i = 0; i <= zhang; i++) {// 递归调用，计算使用下一个硬币种类时的结果int next = process(coins, index + 1, rest - coin * i);// 如果next不是Integer.MAX_VALUE，更新最小硬币数if (next != Integer.MAX_VALUE) {min = Math.min(min, i + next);}}// 返回找到的最小硬币数return min;
}

首先获取index下对应的值：coin=coins[index]   然后确定当前值最优可以用几张：zhang=rest/coin

然后设置一个最小值min；开始循环，如果使用当前值i张，那么一共需要多少张零钱。然后求一个最小值。最后返回min；

这里涉及到重复计算，比如数组 coins = [1, 2, 5], amount = 11

重复计算的例子：

• 剩余金额为10时：
  • 可能通过使用0个1元硬币后使用5个2元硬币到达，也可能通过使用10个1元硬币直接到达，都会调用 process(coins, 2, 10)。
• 剩余金额为9时：
  • 可以通过使用1个1元硬币后使用4个2元硬币到达，或者通过9个1元硬币到达，都会调用 process(coins, 2, 9)。
• 剩余金额为5时：
  • 可以通过使用1个5元硬币直接到达，或者使用5个1元硬币，或者使用3个1元硬币后使用1个2元硬币到达，这些都会重复调用 process(coins, 2, 5)。

所以我们可以使用动态规划来解，首先对于这种稍微服务在可以的画一个表格：

行：表示可以使用的元素   列：目标值是多少

dp[i][j]:表示对于数组中的元素从0到i可以用 得到j最少多少张。表格如下：

	0	1	2	3	4	5	6	7	8	9	10	11
1	0	1	2	3	4	5	6	7	8	9	10	11
2	0	1	1	2	2	3	3	4	4	5	5	6
5	0	1	1	2	2	1	2	2	3	3	2	3

找规律：对于dp[i][j]是不使用当前值 nums[i] 达到小还是使用当前值dp[i][j-nums[i]+1 小谁小要谁。

代码如下：

java">public static int coinChange(int[] coins, int amount) {if (coins == null || coins.length == 0) {return -1;}int N = coins.length;int[][] dp = new int[N][amount + 1];// dp[i][j] 表示在下标 0-i这个数组里面 最少需要多少张可以组成j// dp[i][0]==0 java 默认 不用写// 计算dp[0][j] 表示只有一个数的 最少有多少种张组成 那就是能否整除for (int i = 1; i <= amount; i++) {if (i % coins[0] == 0) {dp[0][i] = i / coins[0];} else {dp[0][i] = -1;}}//for (int i = 1; i < N; i++) {for (int j = 1; j <= amount; j++) {dp[i][j] = Integer.MAX_VALUE;if (dp[i - 1][j] != -1) {dp[i][j] = dp[i - 1][j];}if (j - coins[i] >= 0 && dp[i][j - coins[i]] != -1) {dp[i][j] = Math.min(dp[i][j], dp[i][j - coins[i]]+1);}if (dp[i][j] == Integer.MAX_VALUE) {dp[i][j] = -1;}}}return dp[N - 1][amount];}