[LeetCode]Coin Change

和knapsack problem类似的问题，这里求的就是要让背包正好填满所需的最少物品数量。每物品可以用无限多个，所以就是无界背包问题。用DP[i][j]表示用前i + 1个物品填满容量为j的背包所需的最少物品数量，c[i]为第i + 1个物品的体积。那么递推公式为;

• DP[i][j] = min(DP[i - 1][j], DP[i][j - c[i]] + 1)

假设体积为V，物品数量为n，时间复杂度为O(n * V)，空间复杂度可以优化为O(V)，代码如下：

这道题递推公式可以有很多种，比如用DP[i]表示填满容量为i的背包所需的最少物品数量，我们还可以得到另一个递推公式：

• DP[i] = min(DP[i - c[j]] + 1), where c[j]为第j + 1个物品的体积，且c[j] <= i

时间复杂度和空间复杂度同上，代码如下：