Re:Dynamic Programming vs. Divide-and-Conquer (2018)
by limoce on Sunday April 25, 2021 @06:03AM
(#26931578)
Seems you got down-voted. I guess you're doing competitive programming? People that are good at CP never call "recursion with memoization" as "divide and conquer". Yeah, they just call it recursion.
"Divide and conquer" in CP world seems to be specific to those problems whose subproblems are not overlapping (therefore completely "divided"), e.g. merge sort, segment trees.
Considering the classic problem "Tower of Hanoi", is it "divide and conquer"? No to CP people, and even Wikipedia [0] does not explicitly regard it as "divide and conquer".
"Divide and conquer" in CP world seems to be specific to those problems whose subproblems are not overlapping (therefore completely "divided"), e.g. merge sort, segment trees.
Considering the classic problem "Tower of Hanoi", is it "divide and conquer"? No to CP people, and even Wikipedia [0] does not explicitly regard it as "divide and conquer".
[0]: https://en.wikipedia.org/wiki/Tower_of_Hanoi