제가 정확히 아는 게 아닐 수 있지만 애초에 dp의 정의 자체가 어떠한 수가 규칙적으로, 반복적으로 사용되어 그 수를 재사용해서 시간을 아끼자는 알고리즘이니 무슨 문제든 정의할 수 있을 것 같습니다.
님말대로 첫 몇 항의 수를 일일이 나열 후 직관에 따라 규칙을 찾는 것은 논리적인 행동이지만 어떤 문제에서는 적용하기 어려울 수 있습니다. dp[i]=dp[i-1]+2*dp[i-2]를 먼저 떠올린 뒤 이걸 검산하는 쪽으로 생각하는 게 조금 더 좋다고 생각합니다.
여기서 문제는 그래서 dp의 정의가 그런 건 알겠는데 나에게 주어진 문제가 dp[i] 형태로 표현될 수 있나?라는 사실상 표현만 바뀌었지 동일한 문제에 빠진다는 점이고, 표현될 수 있다는 건 알겠는데 그래서 그게 뭔지 모르겠다는 문제에 빠질 수 있다는 점입니다. 개인적으로는 하다보면 손을 댈 수 있습니다라는 답변을 드리고 싶습니다. 추가적으로 하다보면 손을 댈 수 있기는 한데 이게 dp라고? 이게 브루트포스라고? 이게 그리디라고?의 가불기 삼지선다에 빠질 수 있다는 답변 역시 드리고 싶습니다. 뭐 어쩔 수 없죠.

jadahk 1년 전
2×n 타일링문제를 풀 때 dp[x]가 타일을 채우는 방법의 개수일 때,
숫자 x를 1,2로 구성하고 나열할 수 있는 모든 경우의 수와 개수가 같다는 것을 알게되었습니다.
수작업으로 규칙을 찾음 -> 점화식을 만들음 -> 숫자x를 1,2로 구성하고 나열하는 수와 같은것을 알게됨
그러니까 점화식을 만들고 난 다음에 점화식의 원리를 찾아낸겁니다.
(원리라는 표현이 맞는지, 제가 원리라고 하는 것이 제대로 된 분석인지 모르겠습니다)
이 문제는 이전 문제에서 2*2타일의 조건이 추가 되었는데 이를 숫자 x를 1,2-1,2-2로 구성하는 식으로 풀었습니다.
이런식으로 x=5일때 까지 구하고 규칙을 찾아서 점화식dp[i] = dp[i-1] + 2*dp[i-2]을 완성했습니다.
이 문제도 규칙을 찾기 -> 점화식만들기 -> 점화식 이해하기 순으로 진행했습니다.
이렇게 풀고 나니 몇 가지 의문이 생겼습니다.
동적계획법 문제는 이렇게 규칙적인 패턴이 늘 있나요?
그러니까 무슨 문제든 dp[x] = ~~~~~~식으로 정의를 할 수 있나요?
단순히 숫자간의 패턴을 찾아 점화식을 만들어 푸는 방식은 한계가 있을 것 같아서 글을 씁니다.
알고리즘을 많이 공부하진 않았지만 특히 다이나믹 프로그래밍은 뭔가 직관적이지 않은 것 같습니다.
이런 저런 문제를 풀어내도 다른 유형의 문제를 마주치면 손도 못댈거같은 느낌이드네요.