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

Answer 1

参考回答：

给定一组硬币数，找出一组最少的硬币数，来找换零钱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;
else
return minNumber[amount];
}

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