Timeline for How is Dynamic programming different from Brute force
Current License: CC BY-SA 3.0
2 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 9, 2014 at 18:14 | comment | added | Ben Voigt | And then there's removing a candidate from consideration without fully processing it. For example, finding the set of non-negative numbers with the minimum sum, you don't actually have to sum each set completely, only go until the sum exceeds the current best. This is a similar idea to pruning but orthogonal. Combining the two ideas yields "branch-and-bound", where a problem of reduced complexity is solved and used to justify pruning. | |
| Apr 9, 2014 at 16:51 | history | answered | Yuval Filmus | CC BY-SA 3.0 |