[동적계획법]사다리 올라가기

동적 계획법은 전체 문제를 나눈 sub problems들이 각각 최적 부분해를 가지고 있어야한다. 동적 계획법을 잘 풀기 위해서는 3부분 5단계로 풀어 나가야 한다.

1. 문제의 문맥을 이해 => 1)문제 정의, 2) 일반화
2. 누구나 계산 없이 풀 수 있는 기저조건 설정 => 3)기저조건 설정
3. 빠지는 Case가 없도록 재귀식 구성 => 4)재귀식 도출, 5)코딩

특히 재귀식을 구성할 때는 마지막에서 거꾸로 보는 연습과 각 부분 문제의 해가 이미 구해져 있다는 믿음이 중요하다

동적 계획법에 잘 알려진 몇가지 문제들을 풀어보며 각 상황별로 어떻게 문맥을 이해하고 어떻게 case를 만들어 나가야하는지 마치 정석책의 예제처럼 풀어나가보려고 한다

Q. n개의 가로 막대가 있는 사다리를 순서대로 한번에 한 칸 또는 두 칸씩 올라 갈 수 있다. 이 사다리를 올라 가는 방법의 수는?

1. L(n) : n개의 가로막대가 있는 사다리를 올라가는 경우의 수
2. L(i) : 0 < i <= n 일때 경우의 수
3. 기저 조건 :
   L(1) = 1 , 1칸 올라가는것 + 한번에 2칸 올라가는것
   L(2) = 2 , 1+1, 2
4. 재귀식 도출 (거꾸로, case 별) :
   L(i) 번째 칸에 도착하기 위해서는
   1) L(i-1)에서 한칸만 올라오거나 , 2) L(i-2)에서 한번에 2칸 올라 올 수 있음
   1) 과 2) 를 더하면 결국 L(i)번째 도착 할 수 있는 전체 경우의 수 인데
   이때, 부분 문제인 L(i-1)과 L(i-2)는 이미 구해져 있다는 믿음으로 이전 부분 집합에서 어떤 연산이 일어 났는지는 고민하지 않는다.
   최종 적으로 재귀식을 만들면,

   L(i) = L(i-1) + L(i-2)

   왜냐면, i 번째 칸에 도착하기 위해서는 i-1에서 오거나 i-2 에서 2칸을 뛰어서 오는 case밖에 없기 때문이다

5. 코딩