Cả DP lẫn greedy đều cần optimal substructure. Sự khác biệt: greedy còn yêu cầu tính chất greedy-choice (một tối ưu cục bộ là tối ưu toàn cục), trong khi DP cần thiết khi bạn phải xem xét nhiều lựa chọn và các bài toán con chồng lấn.
Sự khác biệt
Có optimal substructure? -- cả hai đều cần
+ tính chất greedy-choice có thỏa? -> GREEDY (nhanh, một lượt lựa chọn)
+ phải so sánh nhiều lời giải con / chúng chồng lấn? -> DYNAMIC PROGRAMMING
