이 문제가 다이나믹 프로그래밍 분류에 있어서 다이나믹으로 풀려고 고민을 해보았는데, 부분해가 최적해가 되는지도 모르겠고, 딱히 그럴 이유도 모르겠습니다.

제 생각에는 그래프 연결문제인것 같습니다. 현재 푼 상태긴 한데 

고수님들 부디 알려주실래요?