[DP/동적계획법] 백준 14495 피보나치 비스무리한 수열 - 파이썬(Python)

[ Contents ] 1. 문제 (링크 참조) 14495번: 피보나치 비스무리한 수열 피보나치 비스무리한 수열은 f(n) = f(n-1) + f(n-3)인 수열이다. f(1) = f(2) = f(3) = 1이며 피보나치 비스무리한 수열을 나열하면 다음과 같다. 1, 1, 1, 2, 3, 4, 6, 9, 13, 19, ... 자연수 n을 입력받아 n번째 피보 www.acmicpc.net 2. 문제 풀이 f(n) = f(n-1) + f(n-3) 피보나치 수열 f(n) = f(n-1) + f(n-2)와 달리, f(n-3)이 들어간 수열입니다. 피보나치 수열과 마찬가지로, 점화식만 수정해서 DP로 구현합니다. 3. 코드 # 입력 n = int(input()) # DP cache = [1, 1, 1] for i..

원문링크 : [DP/동적계획법] 백준 14495 피보나치 비스무리한 수열 - 파이썬(Python)