Combination sum 迭代

hfzhangql 发表于 2014-11-4 11:34
http://blog.csdn.net/zyfo2/article/details/8592955
这里有个

我个人观点  你非要用DP当然也不是不可以。。。 overall O（n*target） 但每次更新dp[]都要把前面的解读出来，而前面解的数量是很可能呈指数增长的  所以不论从时间 空间复杂度上都没有很大的优势
而且你也看到了 用DP算解的数量多么neat  算解的全集不可避免要ugly。。  

最近也刷这道题，小挖个坟，提供一个从同学那儿学到的DP的思路。DP应该是有两种情况吧，一个是以当前状态更新之后状态，我提供的思路就是这个；另一个是当前状态用之前的状态计算，类似LCS就是这类。虽然听起来似乎一样但是操作起来不一样。
拿个例子说一下，比如给[2,3,7] target = 7.
首先DP需要一个三维数组DP[][][]保存结果，初始化其长度为1+target，因为其中DP[0]的结果需要初始化为[]。然后就从DP[0]开始增长。
DP[0]: []
从左扫到右，0+2和0+3是小于target的，0+7刚好是target，于是更新为：
DP[0]: []
DP[2]: [2]
DP[3]: [3]
DP[7]: [7]
接下来找DP[1]发现没有解，跳过，找DP[2]，更新为：
DP[0]: []
DP[2]: [2]
DP[3]: [3]
DP[4]: [2,2]
DP[5]: [2,3]
DP[7]: [7]
以此类推，最后用DP[target-1]更新完之后，DP[target]就是想要的结果。
不过假设candidates的长度是n，DP中最长的解集个数是m，那么时间复杂度和空间复杂度都是O(n*m*target)了。