4 ms·
You obviously missed this part: Just like with any dynamic programming problem, we need to produce a matrix very nice code, I found it much clearer than th
by klochner 16y ago
You obviously missed this part:
Just like with any dynamic programming problem, we need to produce a matrix
very nice code, I found it much clearer than the blog post
The key intuition is that by considering the items sequentially, you only care about being able to reach a given sum rather than caring about all the subsets that can reach that sum. So the performance is linear in the number of different sums rather than the number of subsets.
- btilly 16y agoNo, I didn't miss that part. I just didn't believe it. See http://en.wikipedia.org/wiki/Dynamic_programming#Dynamic_programming_in_computer_programming http://en.wikipedia.org/wiki/Dynamic_programming#Dynamic_pro.... You will find that having a table is only one of several options. The approach that I took fits the description of the second class of technique there, going bottom up.
- klochner 16y agoI was kidding :) seriously though, what's up with the sort() call?
- btilly 16y agowhat's up with the sort() call? The spec for the problem he was actually trying to solve said that you needed to provide the set of activities in sorted order. The list is generated in no particular order, so I sorted them before returning them. (A Python array sort sorts the array in place.)