알고리즘 질문

[익명(175.118)]

알고리즘 기말고사 시험문제에 다이나믹 프로그래밍으로 풀 수 없는 최적화 문제를 제시하고 그 이유를 제시하시오라는 문제 였는데

최소 스패닝 트리, 부분 문제로 분할 하여도, 사이클의 존재로 Principle of optimality가 성립하지 아니하므로 다이나믹 프로그래밍으로 풀 수 없다라고 답했는데, 

얼추 정답인가요? 

[익명(niggerlife)]

p np 문제 아님? np 문제 몇개 나열하면 되는거 아님? travelling salesman 같은 문제

[익명(175.118)]

아니요 tsp는 다항시간은 아니지만 dp로 풀 수 있습니다. 문제의 요지는 principle of optimality의 성립 여부인 것 같습니다

[익명(niggerlife)]

하도 오래되서 다 까먹음 님말맞임