问题I：
盒子中有n张卡片，上面的数字分别为k1,k2,...,kn。你有4次机会，每抽一次，记录下卡片上的数字，再将卡片放回盒子中。如果4个数字的和等于m。则你就赢得游戏，否则就是输。直觉上，赢的可能性太低了。请你给出程序，判断是否有赢的可能性。
分析：
要求的是能够赢得游戏概率，很明显，若能够求出4个数子和为m的种数（记作T），那么赢的概率就为T/n^4。
这里，将核心部分扩展为问题II。
问题II：
给出n个正整数，从中依次选择k个数，使得和等于m。问：满足要求的选择的种类数。
这里：同一个数字可以使用多次。顺序不一样，种类也不一样。
例如：集合为：{1,2,3,4,5}，k=3，m=4。就有3种选择方式：1+1+2， 1+2+1， 2+1+1。
分析I：
此问题可以暴力枚举解决，但是时间复杂度就是O（n^k)，指数级别。
要求k个数字的和为m的种数，很容易想到了“背包问题”。只是这里，对背包里物品的数量做出了限制，而且对物品的放入顺序也要做出区分。
想到一下解法：
若用f[ki][ni][mi]表示用前ni个数字中选出ki个，和为mi的种数。那么:
f[ki][ni][mi] = f[ki][ni-1][mi] + f[ki-1][ni][mi-v[ni]]
最后的种数即为f[k][n][m]。
但这个解法是错误的，
原因：考虑数字的可重复性，但没有考虑数字的顺序性。不能简单地加上 f[ki-1][ni][mi-v[ni]]，因为第ni个数字的位置是不确定的。
上面的状态转移方程，把问题想复杂了，其实可以用更简单的动态规划结构来求解：
用f[ki][mi]表示用ki个数字得到和为mi的种数。那么：
f[ki][mi] = Σf[ki-1][mi-v[j]]。j=1,2,3...,n。
时间复杂度：O(kmn)， 空间复杂度O(km)
代码：
int getCount(const vector<int> &v, int m, int k){
int n = v.size();
vector<vector<int> > sum(k+1, vector<int>(m+1, 0));
sum[0][0] = 1;
for(int ki = 1; ki <= k; ++ki){
for(int mi = 1; mi <= m; ++mi)
for(int ni = 1; ni <= n; ++ni)
sum[ki][mi] += mi >= v[ni-1] ? sum[ki-1][mi-v[ni-1]] : 0;
}
return sum[k][m];
}
测试代码：
int main() {
int arr[] = {1,2,3,4,5,6,7,8,9,10};
vector<int> v(begin(arr), end(arr));
int n = 5, k = 4;
int count = getCount(v, n, k);
cout << count << " " << count / pow(n, k) << endl;
return 0;
}
补充：
上面的实现，可用仿照背包问题，逆序遍历，来减少空间复杂度。
新的实现：时间复杂度：O(kmn)， 空间复杂度O(m)
int getCount2(const vector<int> &v, int m, int k){
int n = v.size();
vector<int> sum(m+1, 0);
for(int ki = 1; ki <= k; ++ki){
sum[0] = ki == 1 ? 1 : 0;
for(int mi = m; mi >= 0; --mi){
sum[mi] = 0;
for(int ni = 1; ni <= n; ++ni)
sum[mi] += mi >= v[ni-1] ? sum[mi-v[ni-1]] : 0;
}
}
return sum[m];
}
分析II：
from：@陈利人
这个题目最直接的方法就是四重循环遍历，n^4的时间复杂度，比较恐怖，但确实一个很好的起点。不用觉得很丢人，只要我们持续改进即可。
假设a，b，c是k1到kn中的三个数字，是否存在d使得，a+b+c+d=m？d在k1到kn中。和题目中的意思是一样的，变换等式如下：
d = m - a - b - c
如果满足上式，就是说，要在k1到k2中查找d，即：查找m - a - b - c，找到就存在；找不到，就是不存在。查找有线性查找，二分查找等。四重循环最内一层循环，可以认为是线性的查找，如果想更快一些，可以应用二分查找，而二分查找需要k1到kn是排序的，则先对n个数字进行排序，时间复杂度O(nlogn)。然后最内一层循环，改为二分查找，时间复杂度为O(n^3logn)。所以总的时间复杂度为O(n^3logn)。
经过上面的分析，我们可以得到启发，既然可以提出一个d，那么就可以再提出一个c。将a+b+c+d=m转换为c+d=m-a-b。这样，我们可以枚举k1到kn的两个数的和，然后对n2个和，进行排序，时间复杂度为o(n^2logn)。然后遍历n^2个和，设每一个和为pair，查找是否存在m-pair，同样二分查找，时间复杂度为O(n^2logn)。总的时间复杂度为O(n^2logn)。
小结：
分析I的算法更直观一点，分析II的算法更巧妙。
分析I的算法适用于K比较大的情况下，分析II的算法适用与K比较小的的情况下，可以互补。