[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)，代码如下：

	class Solution {
	public:
	int change(int amount, vector<int>& coins) {
	int n = coins.size();
	vector<int> dp(amount + 1, 0);
	dp[0] = 1;
	for(int i = 0; i < coins.size(); ++i)
	{
	int coin = coins[i];
	for(int j = coin; j <= amount; ++j)
	{
	dp[j] += dp[j - coin];
	}
	}
	return dp[amount];
	}
	};

view raw Coin Change II.cpp hosted with ❤ by GitHub