[LeetCode]Coin Change II

knapsack problem的变形。也就是给定多个物品，每个物品不限定数量，找到填满背包总共有多少种组合(同一组数的不同排列仍然算一种，比如，1，1，2和1，2，1和2，1，1都算一种)。我们用DP[i][j]用表示只用前i + 1个物品填满容量为j的背包的组合，c[i]表示第i个物品的体积。那么我们有递推公式：

• DP[i][j] = DP[i - 1][j] + DP[i][j - c[i]]

上面第一项代表用前i个物品填满容量j背包的方法，第二项代表分别用1，2，3...个第i + 1个物品填满j背包的方法数。如果展开第二项，我们可以得到

• DP[i][j] = DP[i - 1][j] + DP[i - 1][j - c[i]] + DP[i - 1][j - 2 * c[i]] + DP[i - 1][j - 3 * c[i]]

每一项就代表分别用0, 1, 2, 3...个第i + 1个物品的组合数。

假设有n个物品，背包总容量为V，时间复杂度为O(n * V)，空间复杂度可以优化为O(V)，代码如下：