Tag Archives: DP

LeetCode Find the Derangement of An Array

LeetCode Find the Derangement of An Array
In combinatorial mathematics, a derangement is a permutation of the elements of a set, such that no element appears in its original position.
There's originally an array consisting of n integers from 1 to n in ascending order, you need to find the number of derangement it can generate.
Also, since the answer may be very large, you should return the output mod 109 + 7.
Example 1:

Input: 3
Output: 2
Explanation: The original array is [1,2,3]. The two derangements are [2,3,1] and [3,1,2].

Note:
n is in the range of [1, 106].


给定一个长度为n的数组[1,2,3,...,n],如果该数组的一个排列中,每个数字都不在它原来的位置了,我们称这个排列是原数组的一个Derangement(错排)。问长度为n的数组,有多少个Derangement。
维基百科关于错排问题有比较详细的解释
假设dp[n]表示长度为n的数组的错排个数,显然dp[0]=1,dp[1]=0,dp[2]=1。如果已经知道dp[0,...,n-1],怎样求dp[n]。考虑第n个数,因为错排,它肯定不能放在第n位,假设n放在第k位,则有如下两种情况:
数字k放在了第n位,这时,相当于n和k交换了一下位置,还剩下n-2个数需要错排,所以+dp[n-2]
数字k不放在第n位,此时,可以理解为k原本的位置是n,也就是1不能放在第1位、2不能放在第2位、...、k不能放在第n位,也就相当于对n-1个数进行错排,所以+dp[n-1]
因为n可以放在1~n-1这n-1个位置,所以总的情况数等于dp[n]=(n-1)(dp[n-1]+dp[n-2])。
这就类似于求斐波那契数列的第n项了,维护前两个变量,不断滚动赋值就好了,时间复杂度O(n),代码如下:

const int MOD = 1000000007;
class Solution {
public:
	int findDerangement(int n) {
		if (n == 0)return 1;
		if (n == 1)return 0;
		long long p = 0, pp = 1;
		for (int i = 2; i <= n; ++i) {
			long long cur = ((i - 1)*(p + pp)) % MOD;
			pp = p;
			p = cur;
		}
		return p;
	}
};

本代码提交AC,用时13MS。

LeetCode Coin Change

LeetCode Coin Change
You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.
Example 1:
coins = [1, 2, 5], amount = 11
return 3 (11 = 5 + 5 + 1)
Example 2:
coins = [2], amount = 3
return -1.
Note:
You may assume that you have an infinite number of each kind of coin.


给定一堆硬币数组coins和一个总数amount,问最少用多少个硬币能凑齐这amount的钱数。每种面值的硬币数量无限。
一开始想到用贪心,即为了使硬币数最少,我们总是用小于等于amount的最大面值的硬币去凑。但是这样得到的结果不是最优的,而且有时候还可能得不到结果。比如coins=[2,5,7,8], amount=19,如果用贪心的思路,首先取8,amount=19-8=11;再取8,amount=11-8=3;再取2,amount=3-2=1;没有硬币可取了,这样就凑不齐19。但是如果不取8,而是取19=7+7+5,则可以用3枚硬币凑齐。
一般不能用贪心得到全局最优解的时候,用DP总是能得到全局最优解的。
假设dp[i]表示凑齐钱数为i最少需要的硬币数,则dp[i]=min(dp[i-coins[j]]+1, dp[i])。这个递推式的意思是说,如果要凑齐钱数i,我们看看能不能用第j个硬币,如果能的话,用之前需要凑齐i-coins[j]的钱数,所以总的硬币数就是凑齐i-coins[j]的硬币数加上1,这个1就是j这个硬币。我们需要遍历所有j求最小。最后dp[amount]就是全局最优解。
完整代码如下:

class Solution {
public:
	int coinChange(vector<int>& coins, int amount) {
		int mmax = amount + 1, ans = mmax;
		vector<int> dp(amount + 1, mmax);
		dp[0] = 0;
		for (int i = 1; i <= amount; ++i) {
			for (int j = 0; j < coins.size(); ++j) {
				if (i - coins[j] >= 0) {
					dp[i] = min(dp[i], dp[i - coins[j]] + 1);
				}
			}
		}
		return dp[amount] >= mmax ? -1 : dp[amount];
	}
};

本代码提交AC,用时33MS。

LeetCode K Inverse Pairs Array

LeetCode K Inverse Pairs Array
Given two integers n and k, find how many different arrays consist of numbers from 1 to n such that there are exactly k inverse pairs.
We define an inverse pair as following: For ith and jth element in the array, if i < j and a[i] > a[j] then it's an inverse pair; Otherwise, it's not.
Since the answer may very large, the answer should be modulo 109 + 7.
Example 1:

Input: n = 3, k = 0
Output: 1
Explanation:
Only the array [1,2,3] which consists of numbers from 1 to 3 has exactly 0 inverse pair.

Example 2:

Input: n = 3, k = 1
Output: 2
Explanation:
The array [1,3,2] and [2,1,3] have exactly 1 inverse pair.

Note:

  1. The integer n is in the range [1, 1000] and k is in the range [0, 1000].

给定一个长度为n的,包含1~n这n个数的数组,问使得逆序对有k个的数组排列有多少种。
使用DP求解。假设dp[n][k]表示长度为n的数组,有k个逆序对的排列数,则:
dp[n+1][k]=dp[n][k]+dp[n][k-1]+dp[n][k-2]+...+dp[n][k-n]
要求n+1长有k个逆序对的排列数,可以在

  • 长度为n,且有k个逆序对的基础上,把第n+1个数放到原序列的末尾,则不增加逆序对,+dp[n][k],xxxx*(xxxx表示原长度为n的序列,*表示新加入的数)
  • 长度为n,且有k-1个逆序对的基础上,把第n+1个数插入到原序列倒数第一个空位上,xxx*x,因为插入的*是最大的数,和最后一个x形成一个逆序对,使得新的长度为n+1的序列的逆序对=k-1+1=k,所以+dp[n][k-1]
  • 类似的,xx*xx,+dp[n][k-2]
  • x*xxx,+dp[n][k-3]
  • *xxxx,+dp[n][k-4]

因为远序列长度为n,所以插入的*最多只能增加n个逆序对,即上面的最后一种情况,所以原序列至少需要k-n个逆序对,这样插入*之后,才能达到k-n+n=k个逆序对。即以上递推式的最后一项是dp[n][k-n]。
完整代码如下,注意代码中i其实是n+1,所以m的下界是k-n=j-(i-1)=j-i+1,所以m>j-i。

const int kMOD = 1000000007;
class Solution {
public:
	int kInversePairs(int n, int k) {
		vector<vector<long long>> dp(n + 1, vector<long long>(k + 1, 0));
		dp[1][0] = 1; // 长度为1,逆序对为0,只有一种情况
		for (int i = 2; i <= n; ++i) {
			for (int j = 0; j <= k; ++j) {
				for (int m = j; m >= 0 && m > j - i; --m) {
					dp[i][j] += dp[i - 1][m];
				}
				dp[i][j] %= kMOD;
			}
		}
		return dp[n][k];
	}
};

本代码提交AC,用时1065MS。时空都还可以优化。
参考:https://discuss.leetcode.com/topic/93710/java-dp-thank-you-so-much-gardenaaa-for-your-advice

LeetCode Unique Substrings in Wraparound String

LeetCode Unique Substrings in Wraparound String
Consider the string s to be the infinite wraparound string of "abcdefghijklmnopqrstuvwxyz", so s will look like this: "...zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd....".
Now we have another string p. Your job is to find out how many unique non-empty substrings of p are present in s. In particular, your input is the string p and you need to output the number of different non-empty substrings of p in the string s.
Note: p consists of only lowercase English letters and the size of p might be over 10000.
Example 1:

Input: "a"
Output: 1
Explanation: Only the substring "a" of string "a" is in the string s.

Example 2:

Input: "cac"
Output: 2
Explanation: There are two substrings "a", "c" of string "cac" in the string s.

Example 3:

Input: "zab"
Output: 6
Explanation: There are six substrings "z", "a", "b", "za", "ab", "zab" of string "zab" in the string s.

给定一个a-z的无限循环字符串s,比如...zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd....。再给定一个字符串p,问p有多少个子串是在s中的。
在s中的子串需要满足一定的条件,比如单个字符可以,还有就是连续的字符串,即abcd...之类的。
注意第二个样例中,p有两个相同的子串c,但是结果中只统计一次,所以比如p中有多个以同一个字符结尾的子串,我们只需要统计最长的那个就好了。比如P="abcdefgxxxxcdefgyyy"。以g结尾的连续子串有两个,分别是abcdefg和cdefg,但是我们只需要保留前者就好了,因为前者最长,它的所有子串已经包含后者的所有子串了。而子串的长度就是以g为结尾且在s中的子串的长度,比如这里就是7。
所以我们只需要统计以每个字符结尾的最长连续子串的长度,然后把所有长度加起来,就是最终结果。
注意abcdefg以g结尾的长度是7,也就是abcdefg有7个子串是在s中的。abcdefg也包含abcdef,以f结尾的长度是6,也就是abcdef有6个子串在s中。
代码如下:

class Solution {
public:
	int findSubstringInWraproundString(string p) {
		vector<int> count(26, 0);
		int len = 0;
		for (int i = 0; i < p.size(); ++i) {
			if (i > 0 && (p[i] - p[i - 1] == 1 || p[i] - p[i - 1] == -25))++len;
			else len = 1;
			count[p[i] - 'a'] = max(count[p[i] - 'a'], len);
		}
		int ans = 0;
		for (int i = 0; i < 26; ++i)ans += count[i];
		return ans;
	}
};

本代码提交AC,用时9MS。

LeetCode Maximal Square

LeetCode Maximal Square
Given a 2D binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area.
For example, given the following matrix:

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

Return 4.


给定一个0,1矩阵,问矩阵中最大的全是1的正方形的面积是多少。
使用DP求解,假设dp[i][j]表示以点(i,j)为右下角的正方形的最大边长,则有dp[i][j]=min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1。
对于点(i,j),我们已经知道以该点的左边、上边和左上角的点为正方形右下角的点能得到的最大的正方形的边长。最好的情况是,如果这三个点能构成的最大正方形的边长相等,则加上点(i,j)之后,边长会扩大1。如下图红色的1,他的左边、上边和左上角的点为正方形右下角的点能得到的最大的正方形的边长都是2,所以加上该红色1之后,最大的边长变成了3。

0 0 0 0 0
0 1 1 1 0
0 1 1 1 0
0 1 1 1 0
0 0 0 0 0

再比如红色1的左边那个点的边长只有1,则红色1最多只能扩展成边长为1+1的正方形。所以这个递推公式是合理的:dp[i][j]=min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1。

0 0 0 0 0
0 1 1 1 0
0 1 1 1 0
0 0 1 1 0
0 0 0 0 0

有递推公式就好办了,直接O(n^2)DP,代码如下:

class Solution {
public:
	int maximalSquare(vector<vector<char>>& matrix) {
		if (matrix.empty() || matrix[0].empty())return 0;
		int m = matrix.size(), n = matrix[0].size();
		vector<vector<int>> dp(m, vector<int>(n, 0));
		int maxLen = 0;
		for (size_t i = 0; i < m; ++i) {
			dp[i][0] = (matrix[i][0] == '1' ? 1 : 0);
			maxLen = max(maxLen, dp[i][0]);
		}
		for (size_t j = 0; j < n; ++j) {
			dp[0][j] = (matrix[0][j] == '1' ? 1 : 0);
			maxLen = max(maxLen, dp[0][j]);
		}
		for (size_t i = 1; i < m; ++i) {
			for (size_t j = 1; j < n; ++j) {
				if (matrix[i][j] == '1') {
					dp[i][j] = min(min(dp[i][j - 1], dp[i - 1][j]), dp[i - 1][j - 1]) + 1;
					maxLen = max(maxLen, dp[i][j]);
				}
			}
		}
		return maxLen*maxLen;
	}
};

本代码提交AC,用时6MS。
因为dp[i][j]实际上只和之前的三个值有关,所以可以节省空间。代码如下:

class Solution {
public:
	int maximalSquare(vector<vector<char>>& matrix) {
		if (matrix.empty() || matrix[0].empty())return 0;
		int m = matrix.size(), n = matrix[0].size();
		vector<int> dp(n + 1, 0);
		int maxLen = 0, last_topleft = 0; // dp[i][j]的左上角那个值
		for (size_t i = 1; i <= m; ++i) {
			for (size_t j = 1; j <= n; ++j) {
				int tmp = dp[j];
				if (matrix[i - 1][j - 1] == '1') {
					dp[j] = min(min(dp[j], dp[j - 1]), last_topleft) + 1;
					maxLen = max(maxLen, dp[j]);
				}
				else {
					dp[j] = 0;
				}
				last_topleft = tmp;
			}
		}
		return maxLen*maxLen;
	}
};

本代码提交AC,用时6MS。

LeetCode Word Break

LeetCode Word Break
Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words. You may assume the dictionary does not contain duplicate words.
For example, given
s = "leetcode",
dict = ["leet", "code"].
Return true because "leetcode" can be segmented as "leet code".
UPDATE (2017/1/4):
The wordDict parameter had been changed to a list of strings (instead of a set of strings). Please reload the code definition to get the latest changes.


给定一个词典和一个字符串,问字符串能否拆分成若干个词典中有的词。比如样例中词典中有leet和code,则给定的字符串leetcode就能拆分成leet和code,他们都在词典中。
使用DP思路。假设dp[j]表示字符串下标j之前的字符串能否拆分成词典中的词的组合。如果要求dp[i],则我们可以看看i之前的所有j,如果有dp[j]是true的,且[j,i)的子串在dict中,说明[0,i)也能被拆分成词典中的词,所以dp[i]=true。最后我们只需要返回dp[n]即可。
对于s="leetcode",dp=1,0,0,0,1,0,0,0,1,所以dp[n]=1。
代码如下:

class Solution {
public:
	bool wordBreak(string s, vector<string>& wordDict) {
		unordered_set<string> dict(wordDict.begin(), wordDict.end());
		int n = s.size();
		vector<int> dp(n + 1, 0);
		dp[0] = 1;
		for (int i = 1; i <= n; ++i) {
			for (int j = i - 1; j >= 0; --j) {
				if (dp[j] && dict.find(s.substr(j, i - j)) != dict.end()) {
					dp[i] = 1;
					break;
				}
			}
		}
		return dp[n];
	}
};

本代码提交AC,用时3MS。

LeetCode Rotate Function

LeetCode Rotate Function
Given an array of integers A and let n to be its length.
Assume Bk to be an array obtained by rotating the array A k positions clock-wise, we define a "rotation function" F on A as follow:
F(k) = 0 * Bk[0] + 1 * Bk[1] + ... + (n-1) * Bk[n-1].
Calculate the maximum value of F(0), F(1), ..., F(n-1).
Note:
n is guaranteed to be less than 105.
Example:

A = [4, 3, 2, 6]
F(0) = (0 * 4) + (1 * 3) + (2 * 2) + (3 * 6) = 0 + 3 + 4 + 18 = 25
F(1) = (0 * 6) + (1 * 4) + (2 * 3) + (3 * 2) = 0 + 4 + 6 + 6 = 16
F(2) = (0 * 2) + (1 * 6) + (2 * 4) + (3 * 3) = 0 + 6 + 8 + 9 = 23
F(3) = (0 * 3) + (1 * 2) + (2 * 6) + (3 * 4) = 0 + 2 + 12 + 12 = 26
So the maximum value of F(0), F(1), F(2), F(3) is F(3) = 26.

给定一个数组A,和函数F(k),其中F(k) = 0 * Bk[0] + 1 * Bk[1] + ... + (n-1) * Bk[n-1],数组B为数组A顺时针旋转k次后的新数组。要求所有F(k)的最大值。
仔细观察样例,会发现F(k)=\sum_{i=0}^{n-1}((k+i)\%n)*a_i。于是可以算出所有的F(k),然后求最大值。代码如下:

class Solution {
public:
	int maxRotateFunction(vector<int>& A) {
		if (A.empty())return 0;
		int ans = INT_MIN, n = A.size();
		for (int k = 0; k < n; ++k) {
			int cur = 0;
			for (int i = 0; i < n; ++i) {
				cur += ((k + i) % n)*A[i];
			}
			ans = max(ans, cur);
		}
		return ans;
	}
};

本代码提交TLE,复杂度是O(kn),遇到大数据时超时了。
如果再仔细研究一下样例,会发现一个更优的递推公式:F(k)=F(k-1)+sum-n*A[n-k]。这样直接根据前一项F(k-1),可以在O(1)时间算出下一项F(k)。总的时间复杂度只有O(n)。代码如下:

class Solution {
public:
	int maxRotateFunction(vector<int>& A) {
		if (A.empty())return 0;
		int n = A.size(), sum = 0, f0 = 0;
		for (int i = 0; i < n; ++i) {
			sum += A[i];
			f0 += i*A[i];
		}
		int ans = f0, pre = f0;
		for (int i = 1; i < n; ++i) {
			int cur = pre + sum - n * A[n - i];
			ans = max(ans, cur);
			pre = cur;
		}
		return ans;
	}
};

本代码提交AC,用时16MS。

LeetCode Palindrome Partitioning

LeetCode Palindrome Partitioning
Given a string s, partition s such that every substring of the partition is a palindrome.
Return all possible palindrome partitioning of s.
For example, given s = "aab",
Return

[
  ["aa","b"],
  ["a","a","b"]
]

本题要求把字符串s分割成若干个子串,使得每个子串都是回文串。如果有多种分割方法,输出所有的分割方案。
很有意思的一道题。我是这样做的:首先用DP求出任意一个子串s[i,...,j]是否为回文串,这就相当于知道了s中那几个位置可以切割;然后就在s中DFS每个割点,求出所有的分割方案。
DP求s[i,...,j]是否为回文串的过程是这样的,如果s[i]==s[j],且dp[i+1][j-1]也是回文串,则dp[i][j]也是回文串。所以我们需要先求到长度比较短的s[i+1,j-1]是否为回文串,然后再求长度更长的是否为回文串。所以在helper函数的外层循环是子串的长度。
求到了任意一个子串是否为回文串之后,DFS每个割点就好了,这个和枚举排列情况很类似,就不再赘述了。完整代码如下:

class Solution {
private:
	void helper(const string& s, vector<vector<int>>& dp) {
		int n = s.size();
		for (int i = 0; i < n; ++i)dp[i][i] = 1; // 单个字符自身就是回文串
		for (int len = 2; len <= n; ++len) {
			for (int i = 0; i + len - 1 < n; ++i) {
				if (s[i] == s[i + len - 1] && ((i + 1 <= i + len - 2 && dp[i + 1][i + len - 2] == 1) || i + 1 > i + len - 2)) {
					dp[i][i + len - 1] = 1;
				}
			}
		}
	}
	void dfs(const string& s, vector<vector<int>>& dp, vector<vector<string>>& ans, vector<string>& cand,int idx) {
		if (idx == s.size()) {
			ans.push_back(cand);
			return;
		}
		for (int i = idx; i < s.size(); ++i) {
			if (dp[idx][i] == 1) {
				cand.push_back(s.substr(idx, i - idx + 1));
				dfs(s, dp, ans, cand, i + 1);
				cand.pop_back();
			}
		}
	}
public:
	vector<vector<string>> partition(string s) {
		int n = s.size();
		vector<vector<int>> dp(n, vector<int>(n, 0));
		helper(s, dp);
		vector<vector<string>> ans;
		vector<string> cand;
		dfs(s, dp, ans, cand, 0);
		return ans;
	}
};

本代码提交AC,用时6MS。

LeetCode Largest Divisible Subset

LeetCode Largest Divisible Subset
Given a set of distinct positive integers, find the largest subset such that every pair (Si, Sj) of elements in this subset satisfies: Si % Sj = 0 or Sj % Si = 0.
If there are multiple solutions, return any subset is fine.
Example 1:

nums: [1,2,3]
Result: [1,2] (of course, [1,3] will also be ok)

Example 2:

nums: [1,2,4,8]
Result: [1,2,4,8]

给定一个数组,求满足这样一个条件的最大子集:该子集中的任意两个元素a和b满足a%b==0或者b%a==0。通过样例能够很好的理解这个题意。
这题的解法和最长上升子序列的求法很类似,用DP求解。首先对数组从小到大排序,然后对于第i个数nums[i],定义dp[i]表示包含nums[i]、满足divisible subset条件、且nums[i]在该子集中是最大元素的子集的最大元素个数。其实就是把dp[i]直观的理解为以nums[i]结尾的满足divisible subset条件的最大子集合的大小。
求解dp[i]的递归方法是,遍历比nums[i]小的所有数nums[j],如果nums[i]%nums[j],则说明nums[i]可以扔到nums[j]所在的子集合中,所以dp[i]=dp[j]+1。遍历所有的j,找一个最大的dp[i]。
因为本题要输出具体的解,所以还定义一个数组parent[i]表示dp[i]的最大值是从哪个j来的。最后输出最优解的时候,j不断的递归往前找即可。
完整代码如下:

class Solution {
public:
	vector<int> largestDivisibleSubset(vector<int>& nums) {
		if (nums.empty())return{};
		sort(nums.begin(), nums.end());
		int n = nums.size(), maxLen = 0, maxIdx = 0;
		vector<int> dp(n, 1), parent(n, -1);
		for (int i = 0; i < n; ++i) {
			for (int j = i - 1; j >= 0; --j) {
				if (nums[i] % nums[j] == 0 && dp[i] < dp[j] + 1) {
					dp[i] = dp[j] + 1;
					parent[i] = j;
				}
			}
			if (dp[i] > maxLen) {
				maxLen = dp[i];
				maxIdx = i;
			}
		}
		vector<int> ans;
		while (maxIdx != -1) {
			ans.push_back(nums[maxIdx]);
			maxIdx = parent[maxIdx];
		}
		return ans;
	}
};

本代码提交AC,用时39MS。
参考:https://www.hrwhisper.me/leetcode-largest-divisible-subset/

LeetCode Combination Sum IV

LeetCode Combination Sum IV
Given an integer array with all positive numbers and no duplicates, find the number of possible combinations that add up to a positive integer target.
Example:

nums = [1, 2, 3]
target = 4
The possible combination ways are:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
Note that different sequences are counted as different combinations.
Therefore the output is 7.

Follow up:
What if negative numbers are allowed in the given array?
How does it change the problem?
What limitation we need to add to the question to allow negative numbers?


给定一个数组,问从数组中有放回的取若干个数字,加起来等于target的方案数有多少种。
一开始以为是和LeetCode Combination Sum是类似的,只不过数字可以重复取而已,于是快速写出了如下的DFS版本:

class Solution {
private:
	void dfs(vector<int>& nums, int sum, int& ans) {
		if (sum == 0) {
			++ans;
			return;
		}
		if (sum < 0)return;
		for (const auto &i : nums) {
			if (sum >= i) {
				dfs(nums, sum - i, ans);
			}
		}
	}
public:
	int combinationSum4(vector<int>& nums, int target) {
		int ans = 0;
		dfs(nums, target, ans);
		return ans;
	}
};

悲剧的是TLE了,给了一个样例[1,2,3],target=32,结果有181997601种之多,DFS确实吃不消。
究其原因还是因为每个数可以重复取值,如果每个数最多取一次,也就相当于0/1背包,每个数可以取或者不取,则用DP很好办:

class Solution {
public:
	int combinationSum4(vector<int>& nums, int target) {
		vector<int> dp(target + 1, 0);
		dp[0] = 1;
		for (int i = 0; i < nums.size(); ++i) { // 对每个数字
			for (int j = target; j >= nums[i]; --j) {
				dp[j] += dp[j - nums[i]]; // 取值;不取dp[j]保持不变;所以取和不取加起来就是+=dp[j-nums[i]]
			}
		}
		return dp[target];
	}
};

但是这题中,每个数是可以重复取值的。因为数组中的数最小是1,所以每个数最多可以取target次,所以我们可以把0/1背包改成最多取target次的背包问题,也就是对于每个商品,我们可以尝试取1次、2次...target次。
我们可以换一种思路,假设dp[i-1]表示生成和为i-1的所有组合数,那么生成和为i的所有组合数等于所有生成和为i-nums[j]的组合数的和,即所有dp[i-nums[j]]的和。dp[i-nums[j]]表示减去nums[j]此时的组合数。
代码如下:

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

本代码提交AC,用时3MS。仔细观察这个版本的代码和上个版本的代码,发现其实就是两层循环换了一下位置,前者求不放回的方案数,后者求放回的方案数。
如果有负数,则要限制每个数的使用次数了,因为如果有数1和-1,要生成和为0的组合数,则可以有无限种,比如[1,-1],[1,1,-1,-1]。