동적 계획법(Dynamic Programming)

주요 전략
- 귀납추론 : 주어진 문제보다 조금 작은 문제들의 답을 안다면 그 것을 이용해서 더 큰 문제의 답을 구할 수 있다!

문제해결 순서

1. 문제 정의 : P(n) : n개의 값에 대한 해
2. 일반화 : 부분문제 정의
3. 기저조건 : P(1)=1, P(2)=2
4. 재귀식 : 거꾸로, 경우로 나눈다 - P(i) = P(i-1) + P(i-2)
5. 코딩


# 사다리 올라가기
# 1칸 또는 2칸 올라갈 수 있음, N층 까지 올라가는 경우의 수

ladder = [1, 2]

n = int(input())
for i in range(2, n):
ladder.append(ladder[i-1] + ladder[i-2])

print(ladder[n-1])

--------------------------------------------------------------------

# 비트 스트리밍
# 1이 연속하지 않는 길이 k의 비트 스트링 수

bit = [2, 3]

n = int(input())
for i in range(2, n):
bit.append(bit[i-1] + bit[i-2])

print(bit[n-1])

--------------------------------------------------------------------

# 최장 증가 부분 수열
# 5 2 8 6 3 6 9 7
# P(k) = 앞에 있는 숫자 중에서 확장 할 수 있는 수 중에 P값이 가장 큰 수

arr = [5, 2, 8, 6, 3, 6, 9, 7]
l = [1]

for i in range(1, len(arr)):
m_len = 0
m_num = 0
for j in range(0, i):
if arr[i] > arr[j]:
if m_len <= l[j]:
m_len = l[j]
if m_len == l[j] and m_num < arr[j]:
m_num = arr[j]

l.append(m_len + 1)
print(max(l))