动态算法求解给定数列的子集数字相加和是否存在一个特定的值。
E.g.【3，34，4，12，5，2】中是否包含和为9的子集，包含则返回true，否则返回false。
动态解法分析：
我们使用bottom up的思想来分析这道题，首先如果，需要找到整个集合中是否包含和为9的子集，我们可以将它拆分为两个情况，一个是把最后这个子集考虑进来：{2,}那么我们可以进一步拆分为，找到除2以外的这些元素里是否有和为9-2的子集，如果存在那么返回true，以此类推，直至推完所以情况，那么还有第二种情况，就是不考虑把2加入进来，那么我们的集合暂时为空{},再往前所有子集中考虑是否存在和为9的子集，这个分析其实也可以说是recursive ，那么如何加入动态编程算法呢，我们考虑这样设计一下，因为上面说的过程，势必会造成很多重复计算，这个无需多说，画个二叉树图就能明白，动态编程的思想就是以空间换时间，如果我们能把一些中间计算结果存储起来，那么下次出现同样的计算就可以直接查找，而不需要再次计算了，时间复杂度大大降低，基于这个考虑，我们设计一个二维数组，s[n][sum+1],这个二维数组有n行，n等于传进来数组的长度，有传入的sum 加1列，每个元素s[i][j]用于保存the
current 和j是否能在传入的set[0]~set[i]的子集中找到和为j的组合，如果可以，保存为true，否则false。
这样我们就很容易想明白，如果我们要查找s[i][j]的值，我们可以是s[i-1][j]如果为真，或者s[i-1][j-set[i]]为真，那么s[i][j]就为真，看下图具体说明：
Case1: s[i][0]以第一列为列，所有元素为true ，基于当sum ==0的时候，我们总有子集为空集时满足这个和为0，s[0][1]表示和为1的时候，当前只包含了子集为{3}的情况下，能不能找到和为1的子集，显然是false的，以此类推，也就是说第一行我们需要单独赋值一下，因为它往上也没有参考lookup，对于第一行：sum[0][j] ~j from 1 to sum,
如果 j !== set[0]那么就为false，否则为true。这样我们设置好了第一行第一列，可以开始考虑lookup其他行列了，以第三行第六列为例：s[2][5]，图中绿色部分，我们是要查找当前包含{4,34,3}的子集中有没有满足和为5的，所有我们考虑，如果{3,34}中包含了和为5的，即上一行的同位元素是满足的，那么我们也满足，即s[2-1][5]（s[i-1][j]）满足，那么下一行也一定满足，同时如果上一行不满足和为5，那么考虑上一行元素里是否满足和为5-set[i]的情况，即s[i-1][sum-set[i]]的情况，这里的sum=j,即s[i-1][j-set[i]]是否出现在之前的集合和中，这里具体就是我们额查看第二行中和为5-4=1的那个元素，s[1][1],两个都是false，那么我们的s[2][5]为false，以此类推，直至推到s[n][9]即可得到结果，返回这个结果即可，那么你会说这样哪里降低时间复杂度了呢，我们只计算了第一行和第一列的计算量，后面的元素都是lookup，查询，时间复杂度为o(1)，大大降低了用recursive的o(n^2)了。我们可以写如下代码：
Int subSetSum(int [] array, int n, int sum){
//n =array.length;
//set thefirst column to true:
boolean [][]res = new boolean [n][sum+1];
for(var i =0;i
m[i][0]= true;
}
//set the first row from res[1~9][0]:
For(var i=1;i<=sum;i++){
If(set[0]!== i)
{ res[i][0] = false}
Res[i][0] = true
}
//startfrom the second line and second column lookup for each element base on //theprevious element:
For(var I = 1; i< n; i++){
For(varj =1; j<=sum;j++){
S[i][j]= s[i-1][j] || s[i-1][j-set[i]]
}
}
Return s[n-1][sum];
}
此外，这道题也可以用递归算法来解，我们来看看，递归怎么做，做完会直观的感受到动态编程思想给程序本身带来的性能的优化：
递归思想是这样的，我们给定一个数列，我们先考虑这样的情况，
假设我们从最后一个元素开始考虑： 那么就有两种情况，一种是我们把最后这个元素包含入进来，假设最终的集合是包含这个元素的，那么我们需要在剩下的集合元素里找到和为 sum – set[n-1]的情况，即isSumSet(set, n-1,sum-set[n-1])
第二种情况是我们不要最后这个元素2，那么问题就转化为了，在集合里前n-1个元素里找到和为sum的子集，即：isSumSet(set, n-1, sum).
递归就是要找到出口，出口在哪里呢，就是 sum为0里就返回true ,否则如果n==0表示遍历完所有元素的所有情况了，sum还不为0，则return false,这个很好理解，比如你当前要找和为9的子集，如果包含最后一个元素的情况下，往上找和为7的子集，如果包含5那么继续找和为2的元素，我们发现再往上找到12的时候，12时大于2的，12不能要，那么继续找，找到4的时候，34，3的时候都不满足，我们会倒回包含2但是不包含5的节点，继续找，12会被排除，因为大于7，假如包含了4，34会被排除，此时和为9-6=3，再找到3的时候和为3-3=0，符合要求了。
以此类推，同时为了减少时间复杂度，我们考虑到如何集合中有元素是大于sum的，那么直接不考虑这个元素，直接跳过它计算下一个元素：isSumSet(set,n-1,sum);
就是这样几种情况。
从下面这个树形结构我们可以看到，里面有很多相同的参数情况，这里就是递归的不高明的地方了，很多重复计算。
递归的写法：
Boolean isSubSet(set, n, sum)
{
//从最后一个元素开始递归
//n=set.length
if（sum==0）
returntrue;
if(n==0&& sum !==0)
returnfalse;
//如果当前元素比和大，那么跳过这个元素：
If(set[n-1]> sum){
isSubSet(set,n-1, sum);
returnisSubSet(set,n-1,sum) || isSubSet(set,n-1,sum-set[n-1]);
}
}
网友评论