[Rosalind] (python) Rabbits and Recurrence Relations

https://rosalind.info/problems/fib/

ROSALIND | Rabbits and Recurrence Relations

 

익숙한 다이나믹 프로그래밍(dynamic programming, dp)를 이용해 풀었다.

# 다이나믹 프로그래밍
def fib(n, k):
    dp = [0, 1, 1]
    for i in range(3, n+1):
        dp.append(k*dp[i-2] + dp[i-1])   
    return dp[n]


with open("rosalind_fib.txt") as f:
    X = f.readline().split(" ")
    n, k = map(int, X)
    print(fib(n, k))

 

문제 이름에 Reccurence Relations이 있음을 보아, 재귀 함수를 이용하는 것이 문제의 의도로 보인다. 보통 재귀를 이용해 이 문제를 푸는 것으로 보인다. 다음은 재귀를 이용한 코드이다.

# 재귀
def fib(n, k):
    if n == 1 or n == 2:
        return 1
    else:
        return k * fib(n-2, k) + fib(n-1, k)


with open("rosalind_fib.txt") as f:
    X = f.readline().split(" ")
    n, k = map(int, X)
    print(fib(n, k))