10844번

틀린 풀이 - 시간초과

import sys

n = int(sys.stdin.reaadline())
cnt = 0
for i in range(10**(n-1), 10**(n)):
    input_list = list(map(int, str(i)))
    for j in range(len(input_list) - 1):
        if abs(input_list[j] - input_list[j+1]) != 1:
            break
    else:
        cnt += 1
print(cnt)

규칙 찾아서

f(n) = f(n-1) + f(n-2)

점화식으로 풀렸다.

1463번

1912번

DP로 풀어야 되는데 어떻게 해야할지 몰랐다

이전 최댓값과(이미 비교 다함) 현재 값을 비교