BackPack Problems - formula + time complexity

Backpack VI

http://www.lintcode.com/problem/backpack-vi/

这题感觉就是一维的，我也是想了想整两维反而整不出来。
最后解了一维方程如下：
I. ret[i] += ret[i - nums[j - 1]];


II. time complexity还是二维的是O(m * n)

因为每次都可以取任一个数，各种反复取，而且最恶心一点是排列组合顺序不同都要算上。
所以不能直接加，而要用for循环加

	for (int i = 1; i <= target; i++) {
	for (int j = 1; j <= n; j++) {
	if (i - nums[j - 1] >= 0) {
	ret[i] += ret[i - nums[j - 1]];
	}
	}
	}

view raw Backpack VI.java hosted with ❤ by GitHub

外层是m或者说target
内层循环是n
所以time complexity是O(m * n)