문제를 보고 이 문제가 dp문제다라는 것을 어떻게 알고 진행하는지 궁금합니다. 다양한 알고리즘이 존재하는데, 따로 문제에서 dp문제라는 주목할만한 힌트가 있나요???

안녕하세요^^문제를 딱 보고 다이나믹이다라고 판단할 수 있는 문제는 LIS, LCS, 냅색 등과 같은 유명한 다이나믹 유형이 아니면 판단하기 힘듭니다. 다이나믹 문제를 많이 풀어보면서 오는 감각이 있습니다. 다이나믹을 잘 하려면 일단은 다이나믹 이외의 다른 알고리즘을 이용해 문제를 푸는 능력이 뛰어나야 합니다. 그래야 어떤 문제를 만났을 때 다른 알고리즘을 적용해보고 안되겠다 싶을 때 다이나믹을 생각해보는 방식입니다.일단 n제한이 커서 효율성을 생각해야 되고, 다른 알고리즘으로는 가능성이 없어보이면 다이나믹을 생각해보면서 점화식이 나올 수 있는지 연구해봅니다.

인프런 커뮤니티 질문&답변

다이나믹 프로그래밍 알고리즘에 대해 질문드립니다.