手写代码：硬币找零问题（要求时间复杂度最佳）

参考回答：

给定一组硬币数，找出一组最少的硬币数，来找换零钱N。

如何减小时间复杂度：不用全局变量来保存计算过的值，也不用递归的方法来实现，用一个一维数组，再用循环来实现。

public int coinChange(int[] coins, int amount) {if (coins == null || coins.length == 0 || amount <= 0)return 0;int[] minNumber = new int[amount + 1];for (int i = 1; i <= amount; i++) {minNumber[i] = amount + 1;for (int j = 0; j < coins.length; j++) {if (coins[j] <= i && minNumber[i - coins[j]] != amount + 1)minNumber[i] = Integer.min(minNumber[i], 1 + minNumber[i - coins[j]]);}}if (minNumber[amount] == amount + 1)return -1;elsereturn minNumber[amount];}

时间复杂度为O(c*n),c是coin的数量，n是amount的值。