그리디 알고리즘과 동적 계획법은 무엇으로 구분하는가?

최적 부분 구조를 가졌으나, 현재의 최적해를 선택하는지 아니면 모든 경우의 수를 고려하여 결정하는지로 구분한다.

그리디는 매 순간 가장 이득인 것을 고르고 뒤를 돌아보지 않는다. 그래서 지금 이득인 선택이 나중을 막는 문제에서는 답을 놓친다.

반면 동적 계획법은 작은 문제의 답을 저장해 중복 계산을 없앤다. 저장하는 방식은 메모이제이션만이 아니라 아래에서 위로 표를 채우는 것도 있다. 최적화가 아닌 경우의 수 세기에도 쓴다.

두 방식의 차이는 문제를 읽는 기준이 된다. 최적 부분 구조가 있는지, 겹치는 부분 문제가 있는지를 먼저 확인하게 만든다.