Dynamic programming & Greedy Algorithm both have the optimal sub-structure.
Dynamic programming usually have several optimal sub-structure at a time and we should choose one or more from them to get the global optimal answer.
It means we should have the sub problem solution first, then choose.
Greedy Algorithm usually have one optimal sub-structure, and we directly choose it and then deal with a smaller problem. Because Greedy ensure us this sub-structure must be in the global optimal answer.
Top-down design method & Bottom-up design method.
Top-down means we have the whole problem, and divide it to several sub-problem, then solve them all.
Bottom-up means we build the global problem directly from small problem, we might do not have the whole picture at all.
Memoization is used for storing solved sub-problem in case they might be solved repeatedly.
DP usually uses Bottom-up method., with memoization.
Greedy usually uses Top-down method, with only one sub-problem.
No comments:
Post a Comment