动态规划（Dynamic Programming, DP）是一种算法策略，它通过将复杂问题分解成更小的子问题来解决，并将子问题的解存储起来，避免重复计算。在本文中，将探讨如何使用自底向上的动态规划方法来解决硬币找零问题。
硬币找零问题要求使用给定的硬币数组，找到组成特定金额所需的最少硬币数量。例如，给定硬币数组 coins = [2, 3, 5] 和目标金额 change = 7，需要找到所有可能的硬币组合，然后选择硬币数量最少的组合。
通过观察，可以发现，对于某些金额的找零，会重复计算。特别是当金额为1和2时，如果目标金额更大，重复计算的情况会更多，这时动态规划的优势就显现出来了。
自底向上的动态规划方法与自顶向下的方法不同，它从最小的子问题开始构建解决方案，直到找到整个问题的解。从金额为0的子问题开始，这是基准情况。然后，使用一个数组来存储这些子问题的解，目标是达到目标金额7。
以金额为1的子问题为例，尝试使用所有给定的硬币（2、3和5），但发现无法组成1的找零。接着，尝试金额为2的子问题，使用2硬币可以完美地组成2的找零，而其他硬币则会导致负数金额，因此跳过它们。
对于金额为3的子问题，发现使用3硬币可以组成3的找零。在金额为4的子问题中，使用2硬币可以组成2的找零，而3和5硬币则无法组成有效的找零。由于已经从底部开始计算并保存了2的找零所需的最少硬币数量，可以直接使用这个结果。
通过这种方式，可以逐步构建出从0到目标金额的找零所需的最少硬币数量。
以下是使用Java语言实现的自底向上动态规划解硬币找零问题的代码：
class Solution {
public int coinChange(int[] coins, int amount) {
int[] cache = new int[amount + 1];
for (int i = 1; i <= amount; i++) {
int minCoins = amount + 1;
for (int coin : coins) {
int remain = i - coin;
if (remain < 0) {
continue;
}
minCoins = Math.min(minCoins, cache[remain] + 1);
}
cache[i] = minCoins;
}
return cache[amount] == amount + 1 ? -1 : cache[amount];
}
}
算法的运行时间取决于目标金额N和硬币数量M。对于每个N值，需要找到所有M值的最少硬币数量，这将给O(N*M)的时间复杂度。空间复杂度为O(N)，因为创建了一个数组来存储从0到N的所有找零计算结果。