Talk:Combinations: Difference between revisions
Content added Content deleted
(→Dynamic programming for enumeration problems: new section) |
m (→Dynamic programming for enumeration problems: Signature) |
||
| Line 8: | Line 8: | ||
== Dynamic programming for enumeration problems == |
== Dynamic programming for enumeration problems == |
||
The gain of dynamic programming for a problem asking to list all solution rather than simply count them is much less than what is suggested by claims such as "The first solution is inefficient because it repeatedly calculates the same subproblem in different branches of recursion." (Haskell) for instance. The asymptotic complexity is the same, O(number of solutions * size of solution). |
The gain of dynamic programming for a problem asking to list all solution rather than simply count them is much less than what is suggested by claims such as "The first solution is inefficient because it repeatedly calculates the same subproblem in different branches of recursion." (Haskell) for instance. The asymptotic complexity is the same, O(number of solutions * size of solution). [[User:Lyxia|Lyxia]] ([[User talk:Lyxia|talk]]) 01:30, 30 April 2017 (UTC) |
||