[LeetCode]Combination Sum IV

和Coin Change II是很类似的，都是knapsack problem的变形问题。唯一的不同就是同一个组合不同的排列也算不同的方法，比如背包容量为4，1，1，2和2，1，1和1，2，1都算不同的。而Coin Change II里这些都算相同的。那么之前的DP方程这一题就不适用了，因为没有办法算不同的排列。我们换一个思路，DP[i]表示背包容量为i的时候填满背包的所有组合数。我们有递推公式：

• DP[i] = sum(DP[i - c[j]])，where c[j]代表第j + 1个物品的体积，c[j] <= i

上面公式代表的是把每一个以c[0],  c[1], c[2]...开头的组合加起来，就是总的组合数。

假设总共n个物品，背包体积为V，时间复杂度为O(V * n)，空间复杂度O(V)，代码如下：

	class Solution {
	public:
	int combinationSum4(vector<int>& nums, int target) {
	int len = nums.size();
	vector<int> dp(target + 1, 0);
	dp[0] = 1;
	for(int i = 1; i <= target; ++i)
	{
	for(int j = 0; j < len; ++j)
	{
	int num = nums[j];
	if(num <= i)
	dp[i] += dp[i - num];
	}
	}
	return dp[target];
	}
	};

view raw Combination Sum IV.cpp hosted with ❤ by GitHub